PA of Algorithms Q61

61The running time of an algorithm is represented by the following recurrence relation:

Which one of the following represents the time complexity of the algorithm?

Option : A
Explanation :
Applying Master’s Theorem
cn > n^{ln₃ 1}
cn > n⁰
Now checking af(n/b) ≤ kf(n) for some k < 1
1*cm/3 ≤ kcn
This is true for k > 1/3
Hence solution is Θ(n).

Forgot your password?

I agree with the Terms.