+3 votes
in Asymptotic Analysis by 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).
by AlgoMeister (1.6k points)
selected by
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...