I have the following worked out:
T(n) = T(n - 1) + n = O(n^2)
Now when I work this out I find that the bound is very loose. Have I done something wrong or is it just that way?
It is O(n^2) .
this is a Geometric series with log(n) terms and each term gets halved. Hence answer is O(N).
These types of recurrence relations can be easily solved using Master Method. For recurrence relation T(n) = 2T(n/2) + cn, the values of a = 2, b = 2 and k =1. Here logb(a) = log2(2) = 1 = k.
Time Complexity =O(1).
You need also a base case for your recurrence relation.
T(1) = c
T(n) = T(n-1) + n
To solve this, you can first guess a solution and then prove it works using induction.
T(n) = (n + 1) * n / 2 + c - 1
First the base case. When n = 1 this gives c as required.
For other n:
T(n)
= (n + 1) * n / 2 + c - 1
= ((n - 1) + 2) * n / 2 + c - 1
= ((n - 1) * n / 2) + (2 * n / 2) + c - 1
= (n * (n - 1) / 2) + c - 1) + (2 * n / 2)
= T(n - 1) + n
So the solution works.
To get the guess in the first place, notice that your recurrence relationship generates the triangular numbers when c = 1:
T(1) = 1:
*
T(2) = 3:
*
**
T(3) = 6:
*
**
***
T(4) = 10:
*
**
***
****
etc..
Intuitively a triangle is roughly half of a square, and in Big-O notation the constants can be ignored so O(n^2) is the expected result.
Think of it this way:
In each "iteration" of the recursion you do O(n) work.
Each iteration has n-1 work to do, until n = base case. (I'm assuming base case is O(n) work)
Therefore, assuming the base case is a constant independant of n, there are O(n) iterations of the recursion.
If you have n iterations of O(n) work each, O(n)*O(n) = O(n^2).
Your analysis is correct. If you'd like more info on this way of solving recursions, look into Recursion Trees. They are very intuitive compared to the other methods.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With