LinuxQuestions.org
Share your knowledge at the LQ Wiki.
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 10-15-2003, 08:15 PM   #1
oulevon
Member
 
Registered: Feb 2001
Location: Boston, USA
Distribution: Slackware
Posts: 438

Rep: Reputation: 30
Finding a real value for constant in Big O notation


I need to find a real value for the constant in Big O notation. For example I know that Insertion Sort takes 0(n^2) in its worst case where there are n(n-1)/2 comparisons. I have tested its worst case (when the array is sorted in descending order) for values of n at 1000, 10000, and 100000. Here are my results:

n= 1000
Time = 15 milliseconds

n = 10000
Time = 913 milliseconds

n = 100000
Time = 146768 milliseconds

My question is how do I apply this data in getting the value of c in the equation
f(n) = c(g(n))

?

Do I graph my results and then keep increasing the constant c until it becomes a tight upper bound for the sort? Any ideas would help, thanks.
 
Old 10-16-2003, 02:32 PM   #2
Claus
Member
 
Registered: Jul 2003
Location: Santiago de Chile
Distribution: Debian testing/unstable
Posts: 74

Rep: Reputation: 15
Look, i think you should use a statistical regression...

Y = a + bt + ct^2

and find the parameters a, b, c.

then if you want constant such that F > y for every t>k,

Y = a + bt + ct^2 < at^2 + bt^2 + ct^2 = (a + b + c)t^2

then, you can say that C = a + b + c is your constant.

I hope you understand me.
 
Old 10-16-2003, 02:37 PM   #3
jharris
Senior Member
 
Registered: May 2001
Location: Bristol, UK
Distribution: Slackware, Fedora, RHES
Posts: 2,243

Rep: Reputation: 47
Damn guys! I thought I escaped this when I graduated - you're bringing my repressed memories back

cheers

Jamie...
 
Old 10-16-2003, 06:11 PM   #4
Claus
Member
 
Registered: Jul 2003
Location: Santiago de Chile
Distribution: Debian testing/unstable
Posts: 74

Rep: Reputation: 15
Dont feel bad man!!! it's just i like a lot maths....

but anyway, I AM NOT SURE if that's what he really wants :S
 
Old 10-16-2003, 06:40 PM   #5
Claus
Member
 
Registered: Jul 2003
Location: Santiago de Chile
Distribution: Debian testing/unstable
Posts: 74

Rep: Reputation: 15
Anyway, now that i think, you dont need to do experimental tests to find the constant.

That constant should be any finite number, doesnt matter how big it is. you just need that your worst case function is always greater than n(n-1)/2.

so, your f(t) = n(n-1)/2 = 1/2(n'2 - n)

and you know that

1/2(n'2 - n) < (n'2)/2

So your constant should be just 1/2.

Now, you can do the testing implementing the sort in some programming language, but listen this: the constant will change with every implementation, machine, etc.

The constant, is just a theoric argument to find the order. but doesn't mean that you always can "trap" the function with that constant.

Sorry if my speach sounds confusing, my english is not very advanced.

See a book of algotithms, it can explain you all that stuffs very well...
 
Old 10-17-2003, 04:41 PM   #6
oulevon
Member
 
Registered: Feb 2001
Location: Boston, USA
Distribution: Slackware
Posts: 438

Original Poster
Rep: Reputation: 30
Thanks for the help. I needed to do the experiments to find a real constant for the growth rate of the function using empirical results. Since the growth rate is O(n^2) all i needed to do was divide elapsed time by n^2 in order to get c at that given n. I made it more difficult than it really was. Thanks for the replies.
 
Old 10-17-2003, 05:04 PM   #7
Claus
Member
 
Registered: Jul 2003
Location: Santiago de Chile
Distribution: Debian testing/unstable
Posts: 74

Rep: Reputation: 15
Intelligent way man
 
  


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
Big O, Big Omega, and Big Theta oulevon Programming 7 05-26-2010 07:18 AM
pointer notation vs array notation? pablowablo Programming 5 03-14-2005 12:34 PM
real big slack problems jr87 Slackware 3 08-20-2003 08:40 PM
Real Programmers Real People Real CS Students nakkaya General 5 07-04-2003 02:46 PM
Need help finding urls of news radio sources for Real player Linux Pcghost Linux - Software 5 05-27-2003 08:58 AM

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

All times are GMT -5. The time now is 02:09 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