what is the time complexity of this code ? (log3n)

user_13968842 0
Viewed 503

I have this code and I have to know the time complexity of it, I am a beginner in this subject and it confuses me a little bit.

void func(int n){
   while(n > 0 && n % 3 ==0){
       do_computation(n);
       n = n/3;
   }
}

the function do_computatation have a time complexity of 1 then the worst case of func would be O(log3n) is that right ?

complexity-theory time-complexity algorithm
1 Answers

Yes, it's O(log3n), but that's the same as O(log n). The base doesn't matter, since logan = (logab)(logbn), and constant factors don't matter.

EDIT:

log(ab) = b log(a) (in any base)

n = blogbn
Take loga of both sides:
logan = loga(blogbn)
=(logbn)(logab)

user_1289400
Related