What is Big O ?

Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.
Reply

Join Date: Sep 2005
Posts: 5
Reputation: mostafa gaber is an unknown quantity at this point 
Solved Threads: 0
mostafa gaber mostafa gaber is offline Offline
Newbie Poster

What is Big O ?

 
0
  #1
Sep 14th, 2005
Please ,
I'm at the 2nd year in computer science dept & i don't know what is
" Big O " and "Algorithm time complexity "
I'd be grateful if anybody answered my Question ..
Reply With Quote Quick reply to this message  
Join Date: Jun 2005
Posts: 2,039
Reputation: Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice 
Solved Threads: 139
Team Colleague
Rashakil Fol's Avatar
Rashakil Fol Rashakil Fol is offline Offline
Super Senior Demiposter

Re: What is Big O ?

 
0
  #2
Sep 14th, 2005
Do you know what it means for two functions to grow at the same speed and for one function to grow faster than another?

The notation O(f) denotes the set of all functions that grow at the same speed as or slower than f. E.g. if the amount of time your program takes to run is 20n*n + 2n + 5, it turns out that your program runs in O(n*n) time, because the function (20n*n + 2n + 5) grows at the same rate as the function (n*n). It is also true that your program runs in O(n*n*n) time, because (20n*n + 2n + 5) grows slower than the cube of n. But saying O(n*n) is more informative. Generally, when people want to know the algorithm time complexity of a program or subroutine, they want to know how long it runs, with respect to some input value. You could give them an exact equation down to the microsecond, but that's not very useful, considering that it'd only be determined for one computer. So it's better to say "the running time grows quadratically with respect to the input size" than "the running time is about 20n^2 + 5n + 2 microseconds." And to say the former, you'd usually use "the running time is O(n^2)."
Reply With Quote Quick reply to this message  
Join Date: May 2005
Posts: 82
Reputation: indianscorpion2 is an unknown quantity at this point 
Solved Threads: 1
indianscorpion2 indianscorpion2 is offline Offline
Junior Poster in Training

Re: What is Big O ?

 
0
  #3
Sep 15th, 2005
Originally Posted by Rashakil Fol
Do you know what it means for two functions to grow at the same speed and for one function to grow faster than another?

The notation O(f) denotes the set of all functions that grow at the same speed as or slower than f. E.g. if the amount of time your program takes to run is 20n*n + 2n + 5, it turns out that your program runs in O(n*n) time, because the function (20n*n + 2n + 5) grows at the same rate as the function (n*n). It is also true that your program runs in O(n*n*n) time, because (20n*n + 2n + 5) grows slower than the cube of n. But saying O(n*n) is more informative. Generally, when people want to know the algorithm time complexity of a program or subroutine, they want to know how long it runs, with respect to some input value. You could give them an exact equation down to the microsecond, but that's not very useful, considering that it'd only be determined for one computer. So it's better to say "the running time grows quadratically with respect to the input size" than "the running time is about 20n^2 + 5n + 2 microseconds." And to say the former, you'd usually use "the running time is O(n^2)."
thank you very much mr.rakhasil fol. i was thinking of posting a thread to get an answer for this question.
Reply With Quote Quick reply to this message  
Join Date: Aug 2005
Posts: 76
Reputation: leelee is an unknown quantity at this point 
Solved Threads: 1
leelee leelee is offline Offline
Junior Poster in Training

Re: What is Big O ?

 
0
  #4
Oct 20th, 2005
Honestly, how do you get to the second year of any CS course and not know what "Big O" and "Algorithm time complexity" are?

In addition, how did you get that far without realising that searching Google for such answers may reveal divine knowledge?
Reply With Quote Quick reply to this message  
Join Date: Jun 2005
Posts: 2,039
Reputation: Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice 
Solved Threads: 139
Team Colleague
Rashakil Fol's Avatar
Rashakil Fol Rashakil Fol is offline Offline
Super Senior Demiposter

Re: What is Big O ?

 
0
  #5
Oct 20th, 2005
That happens if they don't teach it in the first year, if you've switched your major. And when searching on Google, you get three companies calling themselves Big-O Tires, a site Big-O dot com, a Wikipedia article incohesively written by fifty people with their heads up some mathematical rectum, some small government page with a poor explanation, a fan page of a televesion show, and two books -- one about orgasms, the other about basketball.

Then on the second page, we've got a movie, a birding festival, a magazine, some boats, ....

Why are you posting hateful things?
All my posts may be redistributed under the GNU Free Documentation License.
Reply With Quote Quick reply to this message  
Join Date: Aug 2005
Posts: 76
Reputation: leelee is an unknown quantity at this point 
Solved Threads: 1
leelee leelee is offline Offline
Junior Poster in Training

Re: What is Big O ?

 
0
  #6
Oct 20th, 2005
I'm not sure it was hateful at all. It distubs me when people (i) aren't interested in learning; and (ii) aren't interested in researching anything for themselves.

http://www.google.co.uk/search?hl=en...G=Search&meta=
Reply With Quote Quick reply to this message  
Join Date: Jun 2005
Posts: 2,039
Reputation: Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice Rashakil Fol is just really nice 
Solved Threads: 139
Team Colleague
Rashakil Fol's Avatar
Rashakil Fol Rashakil Fol is offline Offline
Super Senior Demiposter

Re: What is Big O ?

 
0
  #7
Oct 20th, 2005
Interestingly enough, your link brings this page back as a result! I like the other Daniweb match a bit more, though.
All my posts may be redistributed under the GNU Free Documentation License.
Reply With Quote Quick reply to this message  
Join Date: Aug 2005
Posts: 76
Reputation: leelee is an unknown quantity at this point 
Solved Threads: 1
leelee leelee is offline Offline
Junior Poster in Training

Re: What is Big O ?

 
0
  #8
Oct 20th, 2005
You're famous.
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:



Similar Threads
Other Threads in the Computer Science Forum
Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC