0
$\begingroup$

I am aware that the algorithm has 1 recursive call of size n/2 and the non-recursive part takes O(log n) time.

Master theorem formula is T(n) = aT(n/b) + O(n^d). In this case a = 1, b = 2, but I am not sure what d is because it is formatted as O(log n), not O(n^d).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You check very carefully whether you can apply the master theorem in this case at all.

Or you just note that T(n) is just the sum of O(log 2^k) for 1 <= k < log n, which equals O(log^2 n).

In general, T(n) = T(n-1)+f(n) is just the sum of f(k) for 0 <= k < n, and for T(n) = T(n/2) + f(n) you just substitute n = 2^n’ then use the same formula.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.