in Algorithms
321 views
0 votes
0 votes

To prove that the time complexity of equation

T(n) = T(α n) + T((1 – α)n) + βn

is

Θ(n logn).

in Algorithms
by
321 views

2 Comments

Form a recurrence tree of this equation with root as βn.....\

at each level u will get cost as βn and height of the tree will be (log β+log n)/logα

so (βn+βn+βn.......up to above hight will be....

=βn*(logβ+logn)/log α

=(βnlogβ)/logα +(βnlogn)/logαΞΘ(nlogn)
0
0
Hint -  Use recurrence tree
0
0

Please log in or register to answer this question.

Related questions