Solve the recurrence relation: T(n)=T(n/2)+T(n^0.5)+n

+3 votes
asked Mar 2 in Asymptotic Analysis by shijie Active (276 points)

1 Answer

+1 vote
Best answer
Simple guess that anyone can make is that T(n) = O(n). This can be proved using PMI.

Further, since T(n) includes n, we know that T(n) = Big Omega(n).  Therefore, we can reach the conclusion that T(n) = Theta(n).
answered Mar 20 by Amrinder Arora (38 points)
selected Mar 28 by shijie
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc