pandey_04's blog

By pandey_04, 5 weeks ago,

What is the time complexity of this recursive function ?

Pseudocode-

def f(n): if n == 0 {return 1} else {return f ( n // 3 ) + f ( n // 3 )}

Using the recursion tree method, my answer comes out to be O(2^log(n)). Log has base 3. Correct me if I am wrong.

If my answer is correct, what does this time complexity mean ?

What will be the closest and more meaningful upper bound ?

How can it be compared with O(n) ?

btw I am solving pashka's A&DS Course- S01E01 home task. Here's the link to blog — link

• -2

 » 5 weeks ago, # |   +3 Don't get carried away by the expression 5 ∗ f ( n // 3 ), it is actually making 1 recursive call in each function call (and not 5), so the tree will have a branching factor of 1 and not 5. The answer would be given by: $T(n) = 1 + T(n/3)$
•  » » 5 weeks ago, # ^ |   +3 Oh right, you mean the result of the recursive call is simply getting multiplied my 5. That makes sense, thanks.
•  » » 5 weeks ago, # ^ |   0 Allow me to reframe the question — What is the time complexity of this recurrence relation ? def f(n): if n == 0 {return 1} else {return f ( n // 3 ) + f ( n // 3 )} The answer comes out to be O(2^logn). Log has base 3.
•  » » » 5 weeks ago, # ^ |   +16 $O(2^{\log_3n}) = O(2^{\log_2n*\log_32}) = O((2^{\log_2n})^{\log_32}) = O(n^{\log_32})$