Question

Assume you have the choice of two algorithms for the same problem, (a) One that reduces a problem of size n in O(n) time to two sub-problems of size in, or (b ) One that solves the problem without any recursion in time O(n2) Which algorithm is faster? Show that if f(n) f(½n) + O(log(n)), then f(n) = O((log n) 4. Write code for a function that takes a nonempty search tree of the form discussed in the class, and returns the key in the largest leaf key-t min leaf (tree node.t t).

algorithms

Answer 1

2) order of 1st algorithm :-

f(n) = 2*f(n/2) + O(n) = 4*f(n/4) + 2*O(n/2) + O(n) = 4*f(n/4) + 2*O(n) ........... = 2^k*f(n/2^k) + k*O(n)

and n/2^k = 1 => k = log(n)

f(n) = nlog(n)

so first algo is faster

3) f(n) < f(n/2)+O(log(n)) < f(n/4) + O(log(n/2)) + O(log(n)) < f(n/4) + 2*O(log(n)) ....... < f(n/2^k) + k*O(log(n))

and n/2^k = 1 => k = log(n)

f(n) = (log(n))²