Complexity

Question 1

What is the master method?

Answer 1

A method for finding the TIME COMPLEXITY of a RECURSIVE algorithm (Θ)

Question 2

What form are the recurrences that we can solve with the master method?

Answer 2

T(N) = aT(n/b) + f(n)
a>=1 subproblems
b> 1 subsets of input
f(n)>0

Question 3

What are the three cases in the master method?

Answer 3

1.f(n) = O (n^(logb(a)- e)), e>0
T(n) = Θ(n^(logb(a)))

2.f(n) = Θ(n^logb(a))
T(n) = Θ(n^(logb(a)) * logn)

3.f(n)= Ω(n^(logb(a)+e))
af(n/b) <= cf(n), c < 1
T(n ) = Θ(f(n))

Question 4

What is the intuition behind the master method?

Answer 4

<= is O
== is Θ
>= is Ω
-Compare f(n) to n^(logb(a))
largest is the solution

Question 5

What is the worst case complexity of binary search? Why?

Answer 5

logn

It is the number of times you have to cut array in half to make it a single element.

Question 6

Give a simple definition of Asymptotic Analysis.

Answer 6

Asymptotic: BEHAVIOUR of function when input gets LARGE. Analysis tries to PREDICT this.

Question 7

Is O(f+g)εO(f)+O(g) true or false?

Answer 7

False
O(n^2+n) =n^2
O(n^2) + O(n) = n^2 + n
There’s no constant to make the first less than the second

Question 8

Is O(fxg) = O(f)x O(g)
True or False?

Answer 8

True
O(n^2 x n) = n^3
O(n^2)x O(n) = n^3

Question 9

What does it mean for f to be Θ(g)?

Answer 9

There’s two constants c1,c2>0 and a No>=N s.t

f is always between c1g and c2g

Question 10

Explain the worst time complexity of mergesort

Answer 10

nlogn. It takes logn splits to SPLIT array into n elements. Then it has to ACCESS each element, which take n time.

Question 11

What do recurrences express?

Answer 11

The running TIME of RECURSIVE algorithms

Question 12

What are the 3 methods we learned to solve recurrences?

Answer 12

1. Master Theorem
2. Substitution
3. Iteration