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