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
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)$$$
Oh right, you mean the result of the recursive call is simply getting multiplied my 5. That makes sense, thanks.
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.
$$$O(2^{\log_3n}) = O(2^{\log_2n*\log_32}) = O((2^{\log_2n})^{\log_32}) = O(n^{\log_32})$$$