15 replies to this topic

[TcM]

I saw this in another thread on this forum and I decided to ask what is this O() notation? Is this language specific or just Advanced Maths?

I didn't want to hijack other threads so I opened my own.

[R-G]

Well, the Landau notation is often used to describe how the size of the digital input data affects an computer software algorithm's usage of computational resources. It is also used in many other scientific and mathematical fields to provide similar estimations.

[WingedPanther]

Expanding on what R-G said:
O() actually defines a family of related functions whose dominant term is less than or equal to the function specified. The technical definition is that a function g(x) is O(f(x)) if there are two constants, C and X, such that for all x>X, g(x) < C*f(x). Usually, people will list the most conservative O() possible for the worst-case scenario.

At work, we had a piece of code that was O(x^2), which ran just fine for our test data (around 100 records), but became very unusable for some of our customers (around 1,000,000 records). The processing time jumped from around 10,000 to around 1,000,000,000,000 time units. When we changed the code to make it O(x), it resulted in drastically improved performance for our larger customers (16 hours down to 15 minutes)

[TcM]

I did not understand much.... I'm not into such advanced levels in Math....

[WingedPanther]

As an example: 5x^2 + 3x+2 is O(x^2). The reason is that 6x^2 > 5x^2+3x+2 when x>4. The x^2 term is the dominant term for 5x^2 + 3x + 2

[TcM]

Yeah, but why 6x^2?

[John]

Because 6x^2 will always be larger than 5x^2+3x+2.

Big oh-notation basically describes how an algorithm acts. Which is why the function Winged described is considered O(x^2).

Take the following code for example:

for(int i = 0; i < n; i++)
    if(i % 2 == 0)
        echo "Even Number";
    }
}

Analyzing this algorithm you might come up with:
`n` assignments [i = 0 each time the loop is ran]
`n` comparisons [ i < n?]
`n` increments [i++]
`n` comparisons [ i % 2 == 0? ]
`1` construct [ echo "Even Number" ]
Assuming each unary or binary operator runs in constant time, this algorithm would really have a `4n` run time. Which is linear. Since Big-Oh only considers how the function acts it is said to be O(n)

[TcM]

Ok so I understood why 6x^2.

So 4n is because n is used 4 times?
And the o() notation ignores the 4?

Sorry, but this is really hard for me...

[John]

It is 4n because there are 4 "instructions" that are ran n times.

Yes, it is O(n) and not O(4n) because the 4 is a constant which is ignored. Both O(4n) and O(n) says the algorithm is linear. Since oh-notation is only used to described how the algorithm grows [linearly, quadratically, exponentially, logarithmically, ect...] the constant has no purpose.

[TcM]

Ok, maybe I understood a little better.

Thanks for your help.

[WingedPanther]

Saying a function is O(6x^2) and saying it is O(x^2) is saying the same thing. The constant multiplier is made irrelevant by the definition of O().

[TcM]

Yeah I understood that :D but now, what is the use of this?