Nov2017 cs Q33

0. Consider the recurrence relation:

Nov2017 cs

Where b and c are constants. The order of the algorithm corrosponding to above recurrence relation is:

Answer
Comment
Array

Option : D
Explanation :
We can use Master theorem to solve this recurrance relation:T(n) = aT(n/2) + Θ(n^klog^pn)
In given question:
T(n) = 8T(n/2) + Cn
here a = 8 and b = 2 and k = 1.
clearly a > b^k
So T(n) = Θ(n^log_ba)
T(n) = Θ(n^{log₂ 8})
ie T(n) = Θ(n³)
So, option (D) is correct.

Forgot your password?

I agree with the Terms.