Big O Notation

Question 1

Why use Big O Notation?

Answer 1

To measure and compare the implementation of algorithms.

Question 2

What is Big O?

Answer 2

Big O allows us to talk about the runtime of an algorithm as the inputs grow

Question 3

What is the formal definition of Big O?

Answer 3

An algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n) as n increases.

Big O measures the worst case of an algorithm: the upper bound.

Question 4

When is an example of O(n^2) occurs?

Answer 4

When a O(n) operation is nested in another O(n) operation. This isn’t O(2N) because O(2N) is when two O(N) operations occur sequentially

Question 5

How to measure the complexity of a loop?

Answer 5

The complexity of a loop is the length of the loop times the complexity of whatever happens inside of the loop.

Question 6

What are the most common Big O run times in ascending order?

Answer 6

O(1) -> O(long n) -> O(n) -> O(n log n) -> O(n^2)

Question 7

What is time complexity?

Answer 7

How we analyze the runtime of an algorithm as the size of the inputs increase

Question 8

What is space complexity?

Answer 8

How much additional memory do we need to allocate in order to run the code in our algorithm?

Question 9

What are the rules of thumb for Big O time complexity?

Answer 9

1. Arithmetic operations are constant.
   2 Variable assignment is constant.
2. Accessing elements in an array or object is constant.
3. In a loop, the complexity is the length of the loop times the complexity of whatever happens inside of the loop

Question 10

What are the rules of thumb for Big O space complexity?

Answer 10

1. Most primitives are constant space.
2. Strings require O(n) space (where n is the string length)
3. Reference types are generally O(n) where n is the length (for arrays) or the number of keys (for objects)

Question 11

What is better: O(n) or O(log n)?

Answer 11

O(log n)