Recursive algorithm. Time complexity

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 995 Views - Last Post: 09 April 2017 - 12:56 PM

#16 Daniel551  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 09-April 17

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 11:50 AM

I would prove that by showing that there is no way to get above 3^n, right? The problem is that I don't know how to do that either :D
Was This Post Helpful? 0
  • +
  • -

#17 jon.kiparsky  Icon User is offline

  • Chinga la migra
  • member icon


Reputation: 10720
  • View blog
  • Posts: 18,353
  • Joined: 19-March 11

Re: Recursive algorithm. Time complexity

Posted 09 April 2017 - 12:56 PM

Are you familiar with proofs by induction? Suppose you've called F1 with some argument n, and you happen to know that F1(n-1) requires some number of calls - call it t, for time. Now, how many calls (t', pronounced t-prime) does F1(n) require, in terms of n-1, in the worst case?

Since this is a proof, feel free to rename things if you want - maybe you'd rather think in terms of F1(n) requires t calls, and you want to find t' for F1(n+1), that's fine.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2