Iterative Logarithm in Recurrence Relation? Anyone Could describe me How we can solve this recurrence relation? T(n)=T(logn)+O(1) T(1)=1 a) O(logn) b) O(log∗n) c) O(log^2 n) d) O(n log n)

Brianna Schmidt

Brianna Schmidt

Answered question

2022-10-13

Iterative Logarithm in Recurrence Relation?
Anyone Could describe me How we can solve this recurrence relation?
T ( n ) = T ( log n ) + O ( 1 )
T ( 1 ) = 1
a) O ( log n )
b) O ( log n )
c) O ( log 2 n )
d) O ( n / log n )

Answer & Explanation

Hamnetmj

Hamnetmj

Beginner2022-10-14Added 21 answers

The notation log n is defined by:
log n = { 0 if  n 1 1 + log ( log n ) otherwise
That looks very much like your recurrence, modulo a constant term (except your recurrence looks like it needs some implicit rounding somewhere in order to make sure you reach the base case).
The TA is right that your T is also O ( log n ), but that is not the best bound among the options. In fact T is in each of the 4 possible complexity classes, but O ( log n ) is the tightest one.
4enevi

4enevi

Beginner2022-10-15Added 5 answers

Maybe this would help (for sake of argument assume O ( 1 ) = 1):
T ( 1 ) = T ( 0 ) + 1
T ( e ) = T ( 1 ) + 1 = T ( 0 ) + 2
T ( e e ) = T ( e ) + 1 = T ( 0 ) + 3
T ( e n ) = T ( 0 ) + n + 1
l o g ( e n ) = n
(where is tetration).
Now take O ( 1 ) = 0, so T ( n ) = O ( l o g ( n ) )

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?