# Recursive algorithm. Time complexity

• (2 Pages)
• 1
• 2

## 16 Replies - 934 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

• Screw Trump (before he screws you)

Reputation: 10625
• Posts: 18,183
• 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.

• (2 Pages)
• 1
• 2

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }