Big O complexity

Question 1

What are the different levels of BigO complexity?

Answer 1

O(log n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2^n)

Question 2

What are the two approaches to time complexity?

Answer 2

Theoretical Analysis - study the number of times the algorithm performs some basic operations

Empirical Analysis - Code and run the algorithm on a computer for some inputs and measure how long it takes

Question 3

How is time complexity calculated

Answer 3

Number of basic operations in terms of the input size.

Question 4

Downsides of Empirical analysis

Answer 4

▶ Depends upon the speed of the computer
▶ A slow algorithm will waste time to test
▶ It is hard to reason about how the algorithm will perform for an arbitrary input (we can’t try all inputs!)

Question 5

What is Worst Case efficiency?

Answer 5

T(n) is the maximum running time (in
terms of number of basic operations) for any input of size n.

Question 6

Rank in terms of efficiency:
Exponential
Constant
Logarithmic
Polynomial

Answer 6

1. Constant O(1)
2. Logarithmic O(log n)
3. Polynomial O(n, n2, n3)
4. Exponential O(2^n)

Question 7

State the formal definition of big-O notation, i.e.:
f (n) ∈ O(g(n)) if

Answer 7

There exists constants c > 0
and n0 > 0
such that f (n) ≤ c · g(n)
for all n > n0