Big-O

Question 1

What is “Big-O” ?

Answer 1

The language and metric we use to describe the efficiency of algorithms.

Also called “Asymptotic Runtime”

Refers to how much time or space an algorithm will use, generally based on an input size “n”

It is a rough upper bound for worst cases and large inputs

Question 2

Common Big-O Runtimes

Answer 2

• O(1) - Constant
• O( log N ) - Logarithmic
• O( N ) - Linear
• O( N log N ) - Log Linear
• O( N² ) - Quadratic
• O( N³ ) - Cubic
• O( 2^N ) - Exponential
• O( N! ) - Factorial

Question 3

Which has the higher complexity?

O(N)

or

O( 1 )

Answer 3

O( N )

Question 4

Which has the higher complexity?

O(N)

or

O( log N )

Answer 4

O( N )

Question 5

Which has the higher complexity?

O(N)

or

O( N log N )

Answer 5

O( N log N )

Question 6

Which has the higher complexity?

O(N log N)

or

O( 1 )

Answer 6

O( N log N )

Question 7

Which has the higher complexity?

O(N²)

or

O( 1 )

Answer 7

O( N² )

Question 8

Which has the higher complexity?

O( N³ )

or

O( 1 )

Answer 8

O( N³ )

Question 9

Which has the higher complexity?

O( 1 )

or

O( 2^N )

Answer 9

O( 2^N )

Question 10

Which has the higher complexity?

O( N! )

or

O( 1 )

Answer 10

O( N! )

Question 11

Which has the higher complexity?

O( log N )

or

O( N log N )

Answer 11

O( N log N )

Question 12

Which has the higher complexity?

O( N² )

or

O( log N )

Answer 12

O( N² )

Question 13

Which has the higher complexity?

O( log N )

or

O( N³ )

Answer 13

O( N³ )

Question 14

Which has the higher complexity?

O( 2^N )

or

O( log N )

Answer 14

O( 2^N )

Question 15

Which has the higher complexity?

O( log N )

or

O( N! )

Answer 15

O( N! )

Question 16

Which has the higher complexity?

O( N )

or

O( N² )

Answer 16

O( N² )

Question 17

Which has the higher complexity?

O( N³ )

or

O( N )

Answer 17

O( N³ )

Question 18

Which has the higher complexity?

O( N )

or

O( 2^N )

Answer 18

O( 2^N )

Question 19

Which has the higher complexity?

O( N! )

or

O( N )

Answer 19

O( N! )

Question 20

Which has the higher complexity?

O( N log N )

or

O( N² )

Answer 20

O( N² )

Question 21

Which has the higher complexity?

O( N³ )

or

O( N log N )

Answer 21

O( N³ )

Question 22

Which has the higher complexity?

O( N log N )

or

O( 2^N )

Answer 22

O( 2^N )

Question 23

Which has the higher complexity?

O( N log N )

or

O( N! )

Answer 23

O( N! )

Question 24

Which has the higher complexity?

O( N³ )

or

O( N² )

Answer 24

O( N³ )

Question 25

Which has the higher complexity?

O( N² )

or

O( 2^N )

Answer 25

O( 2^N )

Question 26

Which has the higher complexity?

O( N! )

or

O( N² )

Answer 26

O( N! )

Question 27

Which has the higher complexity?

O( 2^N )

or

O( N³ )

Answer 27

O( 2^N )

Question 28

Which has the higher complexity?

O( N³ )

or

O( N! )

Answer 28

O( N! )

Question 29

Which has the higher complexity?

O( 2^N )

or

O( N! )

Answer 29

O( N! )

Question 30

Three Major

Complexity Notations

Answer 30

Big O

• O( f(n) )
• Asymptotic Upper bounds
• Algorithm AT LEAST that fast

Big Omega

• Ω( f(n) )
• Asymptotic Lower Bounds
• Algorithm will run AT MOST that fast

Big Theta

• 𝚯( f(n) )
• Combines O and Theta
• Indicates that algorithm is O( f(n) ) AND Ω( f(n) )
• Casual use of Big O often really means Big Theta

Question 31

Three general

Input Cases

Answer 31

• Best Case
  
  • Input is organized in a way that the algorithm runs at the fastest possible speed, with the lowest possible complexity
  • Example: Already sorted array into sorting algorithm
• Worst Case
  
  • Input organized so that algorithm runs at the slowest speed possible, with the highest complexity
  • Example: Reverse sorted array into sorting algorithm
• Expected/General Case
  
  • What the vast majority of real world input will look like

Question 32

Two Types

of

Complexity

Answer 32

Time Complexity

Space Complexity

Question 33

Space Complexity

Answer 33

• The space (typically memory) used by an algorithm
• Also described with Big O notation

Example:

• Array size n -> O(n)
• 2D Array size n x n -> O(n²)
• Call Stack: n recursive calls → O(n)

Question 34

Space Complexity:

Recursion

vs

Iterative(loops)

Answer 34

Space Complexity only increases when memory is being used simultaneously.

• Recursive calls increase complexity, because they add to the stack
• Loops(Iterative) do not increase complexity, memory in the scope of the loop is destroyed each iteration

Question 35

General Formulation

of

Big O

(steps)

Answer 35

1. Describe the Worst Case Input
2. Step through the algorithm, add or multiply runtime of sections
3. Simplify by dropping constants:
   
   1. O(2n) = O(n)
4. Further simplify by only using the most dominant(fastest growing) term:
   
   1. O(n² + n) = O(n²)
5. Consider for each type of operation
6. Simplify amortized cost

Question 36

Types of Code Sections

and their Complexity

Answer 36

Code Section Type

Complexity

Sequential Instruction

O( 1 )

Single Pass through Array/Set

O( n )

Distinct Sequential Loops (e.g. two separate arrays)

O(A + B)

Nested Loops

O(A * B)

Elements Halved (eg Binary Search)

O( log n )

Recursive Function with Multiple calls

O(branches^depth)

Question 37

Complexity of Code Section Types:

Sequential Instruction

Answer 37

O(1)

Constant

Question 38

Complexity of Code Section Types:

Single Pass

through Array/Set

Answer 38

O( n )

Linear

Question 39

Complexity of Code Section Types:

Distinct Sequential Loops

Answer 39

O( A + B)

Where A and B are the number of iterations in two distinct loops

Question 40

Complexity of Code Section Types:

Nested Loops

Answer 40

O( A * B)

Where B is the loop nested inside of loop A

Question 41

Complexity of Code Section Types:

Elements halved

(eg Binary Search)

Answer 41

O( log N)

Logarithmic

Question 42

Complexity of Code Section Types:

Recursive Function

w/ multiple calls

Answer 42

O( branches^depth)

Ex: O( 2^N )

Question 43

Multipart Algorithms:

What is the complexity of this code:

for( a : array A) {}

for( b : array B) {}

Answer 43

In this case, Add the complexity:

O( A + B)

Question 44

Multipart Algorithms:

What is the complexity of this code:

for( a : array A) {

for( b : array B) {}

}

Answer 44

Nested Loop: Multiply

O( A * B)

Question 45

Special Case:

Amortized Time

Answer 45

It allows us to describe that a worst case happens every once in a while. But once it happens, it won’t happen again for so long that the cost is “amortized”.

A costly operation that happens infrequently can effectively be ignored, especially if it becomes less frequent over time.

eg

A Dynamic ArrayList doubles it’s capacity when capacity is reached. Normal insertions are O(1), but insertion with growth is O(N).

The Amortized Time is O(1)

Question 46

O( log N )

Runtimes:

Explanation

Answer 46

Log N comes from repeatedly halving an array or set.

One example is Binary Search.

The total runtime is then a matter of how many steps (dividing N by 2 each time) we can take until N becomes 1.

N/2 + N/4 +…+N/2^k

At one element: 2^k = N

and k is our number of steps

So, k = log₂N

In Big O, the base of log doesn’t matter as the growth rate is similar, so it’s just O(log N)

Question 47

Recursive Runtimes:

Explanation

Answer 47

The runtime is the sum of each level of recursion.

For a function:

f(n) { return f(n-1) + f(n-1) }

Each level branches twice:

2ⁿ + 2^n-1 + … + 2¹ + 2⁰ = 2ⁿ⁺¹ + 1

Applying reductions: O(2ⁿ⁺¹ + 1) = O(2ⁿ)

Question 48

Recursive Runtimes:

Call Tree

Answer 48

A technique for modeling recursive functions,

each node on the tree represents a call or stack frame.

Used with a table to count the number of calls per node.

Runtime is the sum of each level of recursion