LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 09-22-2003, 04:18 AM   #1
oulevon
Member
 
Registered: Feb 2001
Location: Boston, USA
Distribution: Slackware
Posts: 438

Rep: Reputation: 30
Growth of Functions


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?

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.
 
Old 09-22-2003, 05:30 AM   #2
Bebo
Member
 
Registered: Jul 2003
Location: Göteborg
Distribution: Arch Linux (current)
Posts: 553

Rep: Reputation: 31
A sum over 1/n - which is what you seem to be doing - diverges.

Cheers
 
Old 09-22-2003, 05:43 AM   #3
Bebo
Member
 
Registered: Jul 2003
Location: Göteborg
Distribution: Arch Linux (current)
Posts: 553

Rep: Reputation: 31
Agh, I'm SO tired. Of course the sum is defined if n is limited... Hm, a silly upper bound would be n_max, since all the terms - except for the first one - are less than one. A similar silly lower bound would be n_max times 1/n_max, i.e. 1.
 
Old 09-22-2003, 05:54 AM   #4
Bebo
Member
 
Registered: Jul 2003
Location: Göteborg
Distribution: Arch Linux (current)
Posts: 553

Rep: Reputation: 31
Sorry, can't let this one go You should be able to get an estimate by integrating 1/n from something to n_max. The estimate (both upper and lower bounds) would look something like a constant plus ln(n_max), possibly with a shift, like ln(n_max plus another constant).
 
Old 09-22-2003, 07:00 AM   #5
SaTaN
Member
 
Registered: Aug 2003
Location: Suprisingly in Heaven
Posts: 223

Rep: Reputation: 33
T(n)= 1 + 1/2 + 1/3 + 1/4 + ..... + 1/n

Since , f''(x)>0 , where f(x)=1/x for x>0

f(a+1)+f(a+2)+....f(b)<= integral of f(x) over a,b<=f(a)+f(a+1)+....f(b-1)

If a=1 and b=n
We have ,

f(2)+f(3)+....f(n)<=log(n)<=f(1)+f(2)+.....+f(n-1) ---- eq(1)


T(n) <= log(n)+f(1) = log(n)+1 [ Adding f(1) on both sides of L.H.S of eq 1]

T(n)>=log(n)+f(n)[ Adding f(n) on R.H.S of eqn 1 ]

-----------------------------------------
log(n)+1 <= T(n) <= log(n)+ 1/n
-----------------------------------------

I suppose , These are the tightest limits one can achieve...

<edit> I didn't understand ur second question

Last edited by SaTaN; 09-22-2003 at 07:04 AM.
 
Old 09-22-2003, 09:29 PM   #6
oulevon
Member
 
Registered: Feb 2001
Location: Boston, USA
Distribution: Slackware
Posts: 438

Original Poster
Rep: Reputation: 30
Thanks for all your help.
 
Old 09-24-2003, 12:53 AM   #7
eric.r.turner
Member
 
Registered: Aug 2003
Location: Planet Earth
Distribution: Linux Mint
Posts: 216

Rep: Reputation: 31
Re: Growth of Functions

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.
 
Old 09-24-2003, 11:58 PM   #8
oulevon
Member
 
Registered: Feb 2001
Location: Boston, USA
Distribution: Slackware
Posts: 438

Original Poster
Rep: Reputation: 30
Thanks for the detailed response. That cleared a lot up for me.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Slow Linux Growth among Desktop users ? rvijay Linux - General 15 06-28-2006 05:31 AM
the growth of linux Cap'n Skyler Linux - General 45 09-26-2005 02:30 AM
[Research] Linux Growth JockVSJock General 8 04-21-2005 04:36 PM
Great Growth! CMonster LQ Suggestions & Feedback 0 10-19-2004 10:47 AM
Official Word: Growth of Frugal Linux. rvijay General 3 09-02-2004 08:41 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 10:23 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration