Quote:
Originally posted by oulevon
I need to find tight lower and upper bounds for the following
function:
T(n) = T(n-1) + 1/n
I understand that the upper bound would be in Big 0 notation, and the lower bound would be in Big Omega notation, but when it needs to be tight does that mean I need to find a function in Big Theta Notation?
|
Not necessarily. A tight upper or lower bound of T(n) simply means that there can be no "better" or "closer" bound. If you find a function that (multiplied by some constant) serves as both an upper and lower bound then by definition you have found both tight upper
and tight lower bounds...
and the upper and lower bounds are the same order of magnitude! This is what Big Theta is all about. However, you don't
have to find a function in Big Theta to find tight upper and lower bounds. Insertion sort is a good example. Its tight upper bound is O(n^2) and its tight lower bound is Omega(n). On arbitrary inputs, insertion sort runs somewhere between n and n^2. You cannot say that insertion sort is Theta(n^2) because on some inputs it runs in n, blowing the lower bound of n^2. You cannot say that insertion sort is Theta(n) because on some inputs it runs in n^2, blowing the upper bound of n.
Quote:
My second problem is I understand how to do the substitution method on the above recurrence, but I was wondering if anyone could explain the Iteration method or point out some resoureces to check out. Thanks for any help.
|
If I understand what you mean by the Iteration method, you expand the subproblem in subsequent iterations:
Code:
T(n) = T(n-1) + 1/n
T(n) = 1/n + T(n-1)
= 1/n + 1/(n-1) + T(n-2) | since T(n-1) = T(n-2) + 1/(n-1)
= 1/n + 1/(n-1) + 1/(n-2) + T(n-3)
= 1/n + 1/(n-1) + 1/(n-2) + 1/(n-3) + T(n-4)
.
.
.
How many iterations do you do? You stop when it makes no sense to continue! In this case you stop when the last term is 1/1, since T(0) isn't defined for the real numbers. Guess what this gives you. The harmonic series! Any good algorithms book should have an asymptotic analysis of the harmonic series.
Hope that helps.
