3

I'm looking for an upper AND lower bound (or just a theta bound, for that matter).

T(n) = T(n-1) + 1/lg(n)

I'm studying for a test, and this is one of the practice questions I've been stuck on.

0

1 Answer 1

1

I guess that the following expansion will give you the appropriate hint:

T(n) =

= 1/lg(n) + T(n-1)

= 1/lg(n) + 1/lg(n-1) + T(n-2)

= 1/lg(n) + 1/lg(n-1) + 1/lg(n-2) + T(n-3)

= ···

= 1/lg(n) + ··· + 1/lg(n/2) + T(n/2)

= Theta(n/lg(n)) + T(n/2)

Now, use the Master theorem on this new recurrence.

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.