121 Week 14 - Big O Notation

Question 1

Big O formal definition

Answer 1

Let T(n) and f(n) be two positive functions from the integers or the real numbers to the real numbers.
T(n) ε O(f(n)) where T(n) has order of f(n), if there are positive constants M and n₀ such that T(n) ≤ M×f(n) for all n ≥ n₀.

T(n) is O(f(n)) if even as n becomes arbitrarily large, T(n)’s growth is bounded from above by f(n), meaning it grows no faster than f(n).

Question 2

What is Big O used for

Answer 2

Used to establish an upper boundary for the growth of the function T(n) for large n.
This boundary is specified by the function f(n) that is usually
much simpler than T(n).
e.g., f(n) = n or f(n) = n^2

Question 3

How to find big O of an algorithm given T(N)

Answer 3

Find the dominant term in T(N) - the term with fastest rate of growth.
Remove constants from the term.
E.g.,
5 + 0.001n^3 + 0.025n has the dominant term 0.001n^3
Remove constants: n^3
Big O = O(n^3)

Question 4

Sequential loops

Answer 4

Sequential loops are 2 for loops running after each other
Find overall big O by finding big O of each loop and comparing which one to see which is bigger:
O(max(N,M) where O(N) is first loop and O(M) is second loop
If both loops have the same stopping condition, they have the same big O so overall big O is big O of either loop.

Question 5

Nested loops

Answer 5

Nested loops are 2 for loops with one loop running within the other – an inner and outer loop.
Find overall big O by finding inner and outer loop time complexities and multiply them.

Question 6

Non independent loops (inspection approach)

Answer 6

Non independent loops are 2 for loops where the inner loop depends on the outer loop.
Find overall big O by running through the inner loop for different scenarios of the outer loop and finding how many times the inner loop runs. Sum each of these to find overall big O

Question 7

Non independent loops (sigma approach)

Answer 7

Find big O by:
- Re-format the loops to be in the format of the general rule
- Find how many times each for loop executes in sigma notation using the general rule
- Represent the nested loops as a double summation with the inner loop being the inner sigma.
- Solve the double summation by solving the inner summation and substituting it into the outer summation to get T(N)
- Find big O of T(N) to get the overall big O

Question 8

Non-independent nested loops

Answer 8

Nested for loops where inner loops depend on outer loops.
Use the same approach as the sigma notation method for non-independent loops but extend to include all loops