What is Big O ?

[mostafa gaber]

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 ..

[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)."

[indianscorpion2]

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.

[leelee]

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?

[Rashakil Fol]

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?

[leelee]

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&q=what+is+big-O+algorithm+time+complexity&btnG=Search&meta=

[Rashakil Fol]

Interestingly enough, your link brings this page back as a result! I like the other Daniweb match a bit more, though.

[leelee]

You're famous.