A Gentle Introduction to Big O

@JoeKarlsson1 ! 1 Big-O Notation www.joekarlsson.com A Gentle Introduction

@JoeKarlsson1 ! 2 Joe Karlsson @JOEKARLSSON1 @JOEKARLSSON JOEKARLSSON.COM

@JoeKarlsson1 ! 3 How is this going to work?

@JoeKarlsson1 ! 4 What is Big-O?

@JoeKarlsson1 ! 5 Not that big O

@JoeKarlsson1 ! 6 Measures how an app will scale when
you increase the amount of things it operates on

@JoeKarlsson1 ! 7 Or  “How slow is thing gonna go?”

@JoeKarlsson1 ! 8 Why should you care?

@JoeKarlsson1 ! 9 Why should you care? •Two types of
estimation in software •Machine independent •Covers all instances of a problem •Allows us to compare algorithms for a problem

@JoeKarlsson1 ! 10 But most importantly INTERVIEWS!

@JoeKarlsson1 ! 11 Some notes before we jump in

@JoeKarlsson1 ! 12 Complexity === “Time” || “Space”

@JoeKarlsson1 ! 13 •We are talking about really, really big
numbers of elements •We are assuming worst case scenarios for algorithms •Big O can be really hard!

@JoeKarlsson1 ! 14 Constant Time (1)

@JoeKarlsson1 ! 15 O(1): Constant Time No matter how large
the input is, the time taken to run doesn’t change

@JoeKarlsson1 ! 16 Elements Time Big O Complexity Graph (1)

@JoeKarlsson1 ! 17 MRW my code runs in O(1) Excellent!

@JoeKarlsson1 ! 18 O(1): Constant Time

@JoeKarlsson1 ! 19 O(1): Constant Time

@JoeKarlsson1 ! 20 Logarithmic Time (logn)

@JoeKarlsson1 ! 21 O(log n): Logarithmic Time Any algorithm that
cuts the problem in half each time

@JoeKarlsson1 ! 22 Elements Time Big O Complexity Graph (logn)
(1)

@JoeKarlsson1 ! 23 MRW my code runs in O(log n)
Excellent!

@JoeKarlsson1 ! 24

@JoeKarlsson1 ! 25 Linear Time (n)

@JoeKarlsson1 ! 26 O(n): Linear Time The larger the input,
The longer it takes, in an even tradeoff.

@JoeKarlsson1 ! 27 O(n): Linear Time Every time you double
the number of elements, the operation will take twice as long

@JoeKarlsson1 ! 28 Elements Time Big O Complexity Graph (n)
(logn) (1)

@JoeKarlsson1 ! 29 MRW my code runs in O(n) Good

@JoeKarlsson1 ! 30

@JoeKarlsson1 ! 31 Lin Log Time (n log n)

@JoeKarlsson1 ! 32 This one is kinda confusing…

@JoeKarlsson1 ! 33 O(n log(n)): LinLog Time Perform an O(log
n) operation for each item in your input

@JoeKarlsson1 ! 34 O(n log(n)): LinLog Time Most efficient sorting
algorithms are an example of this

@JoeKarlsson1 ! 35 Sorting Algorithm Run Times

@JoeKarlsson1 ! 36 Merge  Sort OK

@JoeKarlsson1 ! 37

@JoeKarlsson1 ! 38 Elements Time Big O Complexity Graph (logn)
(1) (n log n) (n)

@JoeKarlsson1 ! 39 MRW my code runs in  O(n log
n) OK

@JoeKarlsson1 ! 40 Quadratic Time (n2)

@JoeKarlsson1 ! 41 O(n^2): Quadratic Time Basically any double nested
for loop

@JoeKarlsson1 ! 42

@JoeKarlsson1 ! 43 Elements Time (logn) (1) (n log n)
(n) Big O Complexity Graph (n2)

@JoeKarlsson1 ! 44 MRW my code runs in  O(n^2) BAD

@JoeKarlsson1 ! 45 Exponential Time (2n)

@JoeKarlsson1 ! 46 O(2^n): Exponential Time The time taken will
double with each additional element in the input data set

@JoeKarlsson1 ! 47

@JoeKarlsson1 (logn) (1) (n log n) (n) (n2) ! 48
Elements Time Big O Complexity Graph (2n)

@JoeKarlsson1 ! 49 MRW my code runs in  O(2^n) VERY
BAD

@JoeKarlsson1 ! 50 But wait, it gets worse…

@JoeKarlsson1 ! 51

@JoeKarlsson1 ! 52 Factorial Time (n!)

@JoeKarlsson1 ! 53 O(n!): Factorial Time 4! === (4*3*2*1)

@JoeKarlsson1 ! 54 O(n!): Factorial Time Involves doing something for
all possible permutations

@JoeKarlsson1 ! 55 O(n!) Examples • Brute force password crackers
• Traveling Salesman Problem

@JoeKarlsson1 ! 56 Traveling Salesman Problem

@JoeKarlsson1 (logn) (1) (n log n) (n) (n2) (2n) !
57 Elements Time Big O Complexity Graph (n!)

@JoeKarlsson1 ! 58 MRW my code runs in  O(n!) THE
WORST

@JoeKarlsson1 ! 59 How do I get better at Big
O? • Figure out the run time as your write functions. • When reviewing PRs by other devs • Practice!

@JoeKarlsson1 ! 60 • Big O Notation allows us to
compare algorithms for a problem • Big O Can be confusing

@JoeKarlsson1 (logn) (1) (n log n) (n) (n2) (2n) !
61 Elements Time Big O Complexity Graph (n!)

@JoeKarlsson1 ! 62 Questions?

@JoeKarlsson1 ! 63 Live long  and prosper

@JoeKarlsson1 ! 64 Additional Resources • Plain English Explanation of
Big O: • https://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o • Big O [Wikipedia]: • https://en.wikipedia.org/wiki/Big_O_notation • Big O Cheatsheet • http://bigocheatsheet.com/

@JoeKarlsson1 ! 65 Let’s Stay In Touch @JOEKARLSSON1 @JOEKARLSSON JOEKARLSSON.COM

@JoeKarlsson1 ! 66

A Gentle Introduction to Big O

A Gentle Introduction to Big O

More Decks by Joe Karlsson

Other Decks in Technology

Featured

Transcript