| | |
What is Big O ?
Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.
![]() |
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)."
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)."
•
•
Join Date: May 2005
Posts: 82
Reputation:
Solved Threads: 1
•
•
•
•
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)."
•
•
Join Date: Aug 2005
Posts: 76
Reputation:
Solved Threads: 1
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?
In addition, how did you get that far without realising that searching Google for such answers may reveal divine knowledge?
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?
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.
•
•
Join Date: Aug 2005
Posts: 76
Reputation:
Solved Threads: 1
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=
http://www.google.co.uk/search?hl=en...G=Search&meta=
![]() |
Similar Threads
- PHP vs ASP... the big ShOwdOwN (IT Professionals' Lounge)
- Motorola T720 Phone and Verizon Wireless (Cellphones, PDAs and Handheld Devices)
- Big Game need progrmmers (C++)
- Is my sig to big? (Geeks' Lounge)
Other Threads in the Computer Science Forum
- Previous Thread: Help me with this Question
- Next Thread: Help solving the explicit solution for the following recursive expression:
| Thread Tools | Search this Thread |
ai algorithm algorithms amazon assignment assignmenthelp assignments automata battery bigbrother binary bittorrent bletchleypark bomb business cern codebreaker compiler computer computerscience computertrackingsoftware connect conversion csc dataanalysis dataintepretation development dfa dissertation dissertations dissertationthesis dissertationtopic ebook employment energy floatingpoint foreclosure foreclosuresoftware fuel gadgets geeks givemetehcodez government graphics hardware history homeowners homeworkassignment homeworkhelp humor ibm idea internet iphone ipod itcontracts jobs kindle laser laws lsmeans mainframes marketing mobileapplication msaccess nano netbeans networking news os p2p piracy piratebay principles rasterizer research sam-being-cute sas science software spying stephenfry study supercomputer sweden technology textfield turing turingtest two'scompliment uk virus ww2






