Big-O, Big-Theta & Big-Omega

Question 1

Describe the symmetry of Big-Theta

Answer 1

if f_(n) is θ(g_(n)) then g_(n) is θ(f_(n))

Question 2

Define Big-Omega in words. i.e. if g_(n) is Ω(f_(n))

Answer 2

g_(n) is not smaller than f_(n) if there are c and n₀ such that for all n > n₀ we have g_(n) >= c.f_(n). f_(n) is the asymptotic lowerbound for g_(n)

Question 3

If f_(n) is O(h_(n)) & g_(n) is O(h_(n)) then f_(n) + g_(n) is

Answer 3

f(n) + g(n) is O(h(_n))

Question 4

Define BigO in words. i.e. if g_(n) is O(f_(n))

Answer 4

g_(n) is not bigger than f_(n) if there are c and n₀ such that for all n > n₀ we have g_(n) c.f_(n). f_(n) is the asymptotic lowerbound for g_(n)

Question 5

if f_(n) is O(g_(n)) then g_(n) is ?(f_(n))

Answer 5

if f_(n) is O(g_(n)) then g_(n) is Ω(f_(n))

Question 6

if f_(n) is O(g_(n)) then f_(n) + g_(n) is ?

Answer 6

if f_(n) is O(g_(n)) then f_(n) + g_(n) is O(g_(n))

Question 7

How many matrix multiplications are required to compute the n-th power of a matrix?

Answer 7

roughly log₂ n

Question 8

Define BigO using the limit equation

Answer 8

Question 9

Define Big-Theta in words. i.e. if g_(n) is θ(f_(n))

Answer 9

g_(n) has the same rate as f_(n) if there are c₁, c₂ and n₀ such that for all n > n₀ we have c₁.f_(n) = g_(n) = c₂.f_(n)

g_(n) has the same complexity as f_(n)

Question 10

Describe the Transitivity of Big-O, Ω & θ

Answer 10

if f_(n) is O(g_(n)) and g_(n) is O(h_(n)) then f_(n) is O(h_(n)).

Same goes for Ω & θ

Question 11

if f_(n) is θ(g_(n)) then f_(n) is ?

Answer 11

if f_(n) is θ(g_(n)) then f_(n) is both O(g_(n)) and Ω(g_(n))

Question 12

Define Big-Ω using the limit equation

Answer 12

Question 13

Define Big-Theta using the limit equation

Answer 13