Building Recurrence relations in plain readable English

1,1,2,3,5,8,13,21,34,55…
fib(i) = fib(i-1) + fib(i-2)
function printReverse(n) {
if(n > 0) {
console.log(n)
printReverse(n-1)
}
}
10
9
8
7
6
5
4
3
2
1
function printReverse(n){ // If this requires T(n) time
if(n > 0) { // This line executes in constant time = 1
console.log(n) // This line executes in constant time = 1
printReverse(n-1) // This line executes in T(n-1) time
}
}
When n <= 0
T(n) = 1
When n > 0
T(n) = 1 + 1 + T(n-1)
.: T(n) = 2 + T(n-1)
.: T(n) = T(n-1) + 2 ... 1
T(n) = 1            (for n <= 0) // This is our "base case"
T(n) = T(n-1) + 1 (for n > 0)
function fibonacci(n) {  // If this requires T(n) time  
if(n == 0 || n == 1) // This is a constant time operation = 1
return 1 // This is a constant time operation = 1
let i = fibonacci(n-1) // This requires T(n-1) time
let j = fibonacci(n-2) // This requires T(n-2) time
return i+j // This is also a constant time operation = 1
}
When n >= 0 && n <= 1:
T(n) = 1 + 1
Which can be asymptotically written as
T(n) = 1
When n > 1:
T(n) = 1 + T(n-1) + T(n-2) + 1
.: T(n) = T(n-1) + T(n-2) + 2
Which can be asymptotically written as:
T(n) = T(n-1) + T(n-2) + 1

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Aditya Singh

Aditya Singh

I write code. Engineer at CoinDCX.