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

+3 votes
asked Mar 2, 2017 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, 2017 by Amrinder Arora (230 points)
selected Mar 28, 2017 by shijie
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc