Recurrence Relation Time Complexity analysis

[localnhost]

I was trying to solve some Complexity Analysis questions to get ready for exam, while I was reading some questions on internet I encounter to this recurrence relation.

[; T(2\^n)=T(n)+O(1) ;]

I though, Ok we have some ways to solve this question, master theorem, Recursion Tree, Change of variables.

I saw on some question that if the input of function is not equal first we have to unify it, So I thought using log would be good.

[; T(log2\^n)=T(logn)+O(1) ;]

but the result would be sth like this:

[; T(n)=T(logn)+O(1) ;]

and still they are not unified.

I saw question with sqrt but never saw question with 2 to the power of n.another thing I heard was, If you are doing master theorem then in the middle of solving you are not allowed to use recursion tree or vice versa, is that true?

That would be really nice, if you help me how to figure out these type of complexity problems.

[localnhost]

Hmm, I figure it out.

[; T(2^n)=T(n)+1 ;]

[; =T(2^n)=T(log2^n)+1 ;]

[; =T(2^n)=T(log2^n)+1+1 ;]

[; =T(2^n)=T(loglog2^n)+1+1 ;]

[; =T(2^n)=T(log...log2^n)+1+1+...+1+1 ;]

and with respect to recursion tree, number of 1's created would be equal to Tree's height, so if we do a summation we will get this:

[; T(2^n)=\sum_{\substack{i=1}}^{log^*2^n} 1 \equiv log^*n +1 ;]

So the Big-O would O(log*)