pandey_04's blog

What is the time complexity of this recursive function ?
By pandey_04, 3 years ago, In English

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

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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)$$$

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Oh right, you mean the result of the recursive call is simply getting multiplied my 5. That makes sense, thanks.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      $$$O(2^{\log_3n}) = O(2^{\log_2n*\log_32}) = O((2^{\log_2n})^{\log_32}) = O(n^{\log_32})$$$

      → Reply