Блог пользователя pandey_04

Автор pandey_04, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +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)$$$

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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.