The Oh Family

Question 1

What do the terms ‘best’, ‘average’ & ‘worst’ mean when it comes to run time?

Answer 1

best = the best runtime given the best situation
worst = the worst runtime given the absolute worst situation
average = the general runtime of a general situation

Question 2

What is the definition of big-Oh?

Answer 2

f(n) is O(g(n)) if and only if there exists positive constants c and n0, such that:
f(n) <= c x g(n) for all n >= n0

Question 3

What properties does big Oh have?

Answer 3

It is reflexive & transitive, but not symmetric

Question 4

What is the multiplication rule for big Oh?

Answer 4

If f1(n) is O(g1(n)) & f2(n) is O(g(n)), then there exists positive constants c1, c2, n1, n2.
Let n0 = max(n1, n2), then multiplying gives f1(n) x f2(n) <= c1 x c2 x g1(n) x g2(n) for all n >= n0

Question 5

What is the rule consisting of dropping smaller terms in big Oh?

Answer 5

If a function tends towards 0 as n tends towards infinity, then you can effectively ‘discard’ that function from the equation.

Question 6

What are the two ‘rules’ for big Oh?

Answer 6

Drop lower-order terms e.g. n if there is an n^2 present
Drop constant terms i.e. numbers such as 5

Question 7

What are the 7 important functions to know for Big Oh?

Answer 7

In order of smallest to biggest:
Constant (1)
Logarithmic (log n)
Linear (n)
N-log-N (n log n)
Quadratic (n^2)
Cubic (n^3)
Exponential (2^n)

Question 8

What does it mean by ‘exponents vs powers’?

Answer 8

Exponentials grow faster than powers. To cancel out a power, use an exponential e.g. 2^n to cancel n^2

Question 9

What does it mean by ‘powers vs logs’?

Answer 9

Powers grow faster than any power of a log. To cancel a log, you use any power, typically n^2, but whatever you have present will do

Question 10

What are some big Oh conventions?

Answer 10

Use the smallest ‘reasonable’ possible class of functions
Use the simplest expression of the class

Question 11

What are the other members of the big Oh family?

Answer 11

Big Oh (O)
little-oh (o)
Big-Omega (Omega)
Big-Theta (Theta)

Question 12

What is the definition of big-Omega?

Answer 12

f(n) is Big-Omega(g(n)) if there are positive constants c and n0 such that:
f(n) >= c g(n) for all n >= n0

Question 13

What are big-Omega’s properties?

Answer 13

Reflexive, Transitive, not symmetric

Question 14

What is the definition of big-theta?

Answer 14

f(n) is Big-Theta(g(n)) if there are positive constants c, c’ and n0 such that:
f(n) <= c g(n)
f(n) >= c’ g(n)
for all n >= n0

Question 15

What are the properties of Big-Theta?

Answer 15

Reflexive, transitive and symmetric

Question 16

What is the definition of little-oh?

Answer 16

f(n) is o(g(n)) if for all positive constants (c > 0), there exists n0 such that f(n) < c g(n) for all n >= n0

Question 17

How does the multiplication rule work with big-Oh * little-oh?

Answer 17

If f1(n) is O(g(n)) and f2 is o(g(n)), then there exists positive constants c1 > 0 and n1, such that:
Exists c1 > 0 exists n1, f1(n) <= c1 g(n) for all n >= n1
For all c2 > 0, exists n2, f2(n) < c2 g2(n) for all n >= n2
Then multiplying gives:
Exists c1 for all c2, exists n1 exists n2, n0 = max(n1, n2):
f1(n) f2(n) < c1 c2 g1(n) g2(n) for all n >= n0
Hence, f1(n) f2(n) is o(g1(n) g2(n))