RunningTime Flashcards
1
Q
Prove using induction that T(n) = 2T(n/2)+n, T(1)=1 is O(nlogn).
A
2
Q
Why is it wrong?
A
- It is wrong because we need to prove the exact form of the inductive hypothesis.*
- That is, that T(n)<=cn*
3
Q
- Given that T(n) = 2T(n/2)+n is O(nlogn)*
- Find the running time of the attached recursion.*
A
4
Q
define exactly a “tight bound”, using f(n) is in Omega(g(n))
A
5
Q
Define in-place algorithm.
A
An algorithm which stores only a constant number of elements of the input array outside the array.
That is, it uses O(1) additional memory.
6
Q
Explain the master theorem
A
7
Q
Solve T(n) = T(n/3) + T(2n/3) + cn using recursion tree
A
8
Q
Using recursive tree method
A
