So I'm currently taking Algorithms course and I'm having an issue solving recurrences and obtaining the running time. I was wondering if someone could explain it to me in layman terms how to solve using substitution method.
Question from the book: Algorithm B solves problems of size n by recursively solving two subproblems of size n − 1 and then combining the solutions in constant time.
Which led me to coming up with the following recurrence: T(n)=2T(n-1)+O(1). I then came up with O(1)=1. Which gave me the following: T(n)=2T(n-1)+1
Here's my attempt at solving it
T(n)=2T(n-1)+1
=2(2T(n-2)+1)+1=4T(n-2)+3
=4(2T(n-3)+1)+3=8T(n-3)+7
=8(2T(n-4)+1)+7=16T(n-4)+15
=16(2T(n-5)+1)+15=32T(n-5)+31
=32T(2T(n-6)+1)+31=64T(n-6)+63
If I'm doing it right, how do I continue to get the running time? Can someone explain in layman terms how to use the substitution method?
You're close, but you can format your back substitution so it makes a bit more sense:
T(n)
=2^1T(n-1)+(2^1-1)
=2^2T(n-2)+(2^2-1)
=2^3T(n-3)+(2^3-1)
=2^4T(n-4)+(2^4-1)
=2^5T(n-5)+(2^5-1)
=2^6T(n-6)+(2^6-1)
...
You can see a pattern here as n approaches 0. It becomes something like 2^n + 2^n - 1, and in Big-O notation, O(2^n).
Some insight that I had that might help you with other recurrence relations: the recurrence happens n times and each iteration multiplies by 2. Sounds something like 2^n!