Big O notation.

[SallyAnne]

Does anyone know anything about this?

I'm really struggling to learn it - I dont know if it's cause I dont have a maths background or what...but it's making my eyes bleed.

All I've got to do is use it to classify addition....and I just can't get my head round it at all!!!!

[EternalOptimist]

Does anyone know anything about this?

I'm really struggling to learn it - I dont know if it's cause I dont have a maths background or what...but it's making my eyes bleed.

All I've got to do is use it to classify addition....and I just can't get my head round it at all!!!!

Sod that. What did you end up doing over the weekend Sally ?

[Francko]

Does anyone know anything about this?

I'm really struggling to learn it - I dont know if it's cause I dont have a maths background or what...but it's making my eyes bleed.

All I've got to do is use it to classify addition....and I just can't get my head round it at all!!!!

[FSM with Cheddar]

I thought the thread was going to be something about orgasms

[suityou01]

I thought the thread was going to be something about orgasms

Roy Orbison

[SallyAnne]

Sorry - was that me trying to talk about something relating to computing again?

What a nob I am - when will I learn?!!

[TimberWolf]

In CS It's often used as a measure of how long a function will takes to compute. The stuff inside the O representing the highest (most significant) order term in an equation that describes how long a function would take to run given a size of input n. In some case a function would run in constant time irrespective of the size of n and other cases would become much slower to run as the size of n increases. You often need to know.

E.g. Some examples from quickest to slowest:
Constant time: O(1)
Searching an already sorted list: O(n log n)
Linear time (e.g. searching an unordered list): O(n)
Quadratic time (some slow sorts) : O(n^2)
Exponential time: O(n!)
etc

Addition would be O(n) because the the problem only gets slower in direct proportion to the number of bits/bytes being added, and multiplication could be as high as O(n^2). The latter (quadratic time) not being too bad, at least compared to exponential functions, but not as fast as linear or constant time algorithms.

[The Lone Gunman]

I think what you need Sal is all explained in "The story of O"

[Francko]

Sorry - was that me trying to talk about something relating to computing again?

What a nob I am - when will I learn?!!

SA, what is this obsession with anything that is big?

[OwlHoot]

There's a Wikipedia article here.

Writing f(x) = O(log(x)) for example just means that for sufficiently large x, |f(x)| is less than C.log(x) for some constant C.

Likewise, if f(x) is a polynomial, say x^n + .. + x + 5 then f(x) = O(x^n), because for sufficiently large x the leading term (with the highest power) dominates all the others however large their coefficients, and this argument can easily be formalized:

|a_n.x^n + .. + a_1.x + a_0| <=

<= |a_n.x^n| + .. + |a_1.x| + |a_0|

<= |a.x^n| + .. + |a.x| + |a| where |a| = max(|a_i|)

= |a| . (|x^n| + .. + |x| + 1)

<= |a| . (|x^n| + .. + |x^n| + |x^n|)

= (n+1) . |a| . |x^n|

So the constant C can be taken as (n + 1).|a|