Recursive algorithm. Time complexity

• (2 Pages)
• 1
• 2

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

#16 Daniel551

Reputation: 0
• 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

#17 jon.kiparsky

• Beginner

Reputation: 11069
• Posts: 18,907
• 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.