Big O notation

[K.I.L.E.R]

If I have a recursive function:

f = n ^ 2 + f(n-1)

Big O:

f = O(n^2);

I understand you take out the multiplier of the largest growing function, and stick the fastest growing part inside a Big O.

WTF does this actually accomplish?
It's not very helpful.

 

[digitalwanderer]

See? Posts like this keep making me think you're smart too.

 

[BRiT]

It gives you order of magnitude based on your domain. Thus if your domain is doubled, you have a general idea of how the performance of an algorithm will scale. Thus if you have a choice of using a O or a O(log) or O(n^2), your choice should be clear in which one to use for performance. Ideally, it would be wonderful to be able to use O(1) algorithms for everything.

Taken from Wikipedia:

The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. More precisely, it is used to describe an asymptotic upper bound for the magnitude of a function in terms of another, usually simpler, function.

In mathematics, it is usually used to characterize the residual term of a truncated infinite series, especially an asymptotic series.In computer science, it is useful in the analysis of the complexity of algorithms.

And here's some goodness from the linked artilcle on Algortihm Effeciency

O(1)

An algorithm that runs the same no matter what the input. For instance, an algorithm that always returns the same value regardless of input could be considered an algorithm of efficiency O(1).

O(logn)

Algorithms based on binary trees are often O(logn). This is because a perfectly balanced binary search tree has logn layers, and to search for any element in a binary search tree requires traversing a single node on each layer.

The binary search algorithm is another example of a O(log n) algorithm. In a binary search, one is searching through an ordered array and, beginning in the middle of the remaining space to be searched, whether to search the top or the bottom half. You can divide the array in half only logn times before you reach a single element, which is the element being searched for, assuming it is in the array.

O

Algorithms of efficiency n require only one pass over an entire input. For instance, a linear search algorithm, which searches an array by checking each element in turn, is O. Often, accessing an element in a linked list is O because linked lists do not support random access.

O(nlogn)

Often, good sorting algorithms are roughly O(nlogn). An example of an algorithm with this efficiency is merge sort, which breaks up an array into two halves, sorts those two halves by recursively calling itself on them, and then merging the result back into a single array. Because it splits the array in half each time, the outer loop has an efficiency of logn, and for each "level" of the array that has been split up (when the array is in two halves, then in quarters, and so forth), it will have to merge together all of the elements, an operations that has order of n.

O(n^2)

A fairly reasonable efficiency, still in the polynomial time range, the typical examples for this order come from sorting algorithms, such as the selection sort example on the previous page.

O(2^n)

The most important non-polynomial efficiency is this exponential time increase. Many important problems can only be solved by algorithms with this (or worse) efficiency. One example is factoring large numbers expressed in binary; the only known way is by trial and error, and a naive approach would involve dividing every number less than the number being factored into that number until one divided in evenly. For every increase of a single digit, it would require twice as many tests.

 

[K.I.L.E.R]

Ta.

Wouldn't a better estimation of time be determined by a generational measure of real time performance?
Plot the results on a graph and then determine which function the graph takes.

 

[bloodbob]

Big O is only in regards to complexity generally either the number of computations required or the storage required.

Now since you've made a recursive function its ugly f = n ^ 2 + f(n-1)
now if we have n=infinity the actual function is
f=n^2+(n-1)^2+(n-3)^2+...+(n-n)^2=n(n+1)(2n+1)/6
Now as n(n+1)(2n+1)/6 tends to infinity the limit is K x n^3
now unless your comparing to algrothims of the same order K is gonna be scale away to nothing as n tends to infinity like Kxn^3/Yxn^2 when n=infinity K&Y don't matter do they.

So the big(O) notation would be O(n^3).

Wouldn't a better estimation of time be determined by a generational measure of real time performance?
Plot the results on a graph and then determine which function the graph takes.

Because there would be major implementation specific factors to take into account and really how trying to work out the function experimentally any better then doing it analytically?

 

[epicstruggle]

Ta.

Wouldn't a better estimation of time be determined by a generational measure of real time performance?
Plot the results on a graph and then determine which function the graph takes.

Yes, but the point is to guesstimate what type of performance any particular algorithm has. God its been ages since i studied big O and all that, im sure someone else can give a better explanation.

epic

 

[BRiT]

Ta.

Wouldn't a better estimation of time be determined by a generational measure of real time performance?
Plot the results on a graph and then determine which function the graph takes.

Not really. In most cases one can just go with the one with the lowest Big-O notation, so long as it doesn't have obscene memory-usage requirements. And in some cases, it's much quicker to just eyeball the code/algorithm to know how it'll perform than it would be in actually performing the runtime analysis. And in most cases when you're evaluating which algorithm to go with or to create, you're not interested in actual real time performance yet.

Its like asking what the fastest way of getting from California to DC is -- walking, cycling, driving, or flying. Sure you could perform that task with each method and measure how long each one takes, but why would you?

 

[K.I.L.E.R]

Thanks.
I would really like to know how you managed to get to Kxn^3.
I lost you in there.

Big O is only in regards to complexity generally either the number of computations required or the storage required.

Now since you've made a recursive function its ugly f = n ^ 2 + f(n-1)
now if we have n=infinity the actual function is
f=n^2+(n-1)^2+(n-3)^2+...+(n-n)^2=n(n+1)(2n+1)/6
Now as n(n+1)(2n+1)/6 tends to infinity the limit is K x n^3
now unless your comparing to algrothims of the same order K is gonna be scale away to nothing as n tends to infinity like Kxn^3/Yxn^2 when n=infinity K&Y don't matter do they.

So the big(O) notation would be O(n^3).


Because there would be major implementation specific factors to take into account and really how trying to work out the function experimentally any better then doing it analytically?

 

[_xxx_]

Because there's a n^3 in this when you multiply all: n(n+1)(2n+1)/6

 

[bloodbob]

Thanks.
I would really like to know how you managed to get to Kxn^3.
I lost you in there.

n(n+1)(2n+1)/6=(n^2+n)(2n+1)/6=(4n^3+2n^2+n^2+n)/6
=(4n^3+3n^2+n)/6

Now as n tends to infinity 4/6n^3 >> (much greater ) 3/6n^2+n/6
so we can discard the insignificant fraction of 3/6n^2+n/6
So your left with 4/6xn^3 which is kxn^3.

 

[K.I.L.E.R]

Sorry I'm a little thick in this area. This is covered work but I'm shocking at it.
What is it called again?
When you expand recursive functions.
It was covered in week 2 but it was about replacing k, with k+1.

I can see you simplifying the equation over a period but why are you dividing by 6?

 

[bloodbob]

When you expand the the recursive function you end up with a simple sum of squares
X^2+(X-1)^2.....+3^2+2^2+1^2

Because in this case you have an infinetly long function I thought I'd do a betterjob then just simple grabbing the highest term ( which would be x^2 and you would end up with a crap answer O(x^2) ). Knowing that an infinite sum of squares must have a nice solution I used google http://www.shu.edu/projects/reals/infinity/answers/sm_sq_cb.html
Which gave me the nice little forumla with the /6.

It got complicated because you used an infinitatly long function. You get similar complications if you expand n!.

You could also come about O(n^3) in another way in each recursion you have n^2 which is O(n^2) and you have n loops which is O. So you have n times n^2 which is OxO(n^2) which is O(n^3).

Also
f=n^2+(n-1)^2+(n-3)^2+...+(n-n)^2=n^2+(n^2-2n-1)+(n^2-4n-4)+(n^2-6n-9)....=n^3+(2n-1)+(4n-4)+(6n-9).....
As n tends towards infinite f tends towards n^3

 

[Simon F]

It gives you order of magnitude based on your domain. Thus if your domain is doubled, you have a general idea of how the performance of an algorithm will scale. Thus if you have a choice of using a O or a O(log) or O(n^2), your choice should be clear in which one to use for performance.

ONLY if n is very large. O doesn't tell you what the coefficients are in front of the terms of the polynomial.

For example, I might have algorithm x which has running time, Tx = n^2 + .... + 100, and algorithm y, with Ty = 10000 n + 10.

If n is "small", then it would be better to choose the O(n^2) ("x") algorithm rather than the O ("y") one.

For example, there exist O(n log n) multiplication algorithms but no-one uses them because the break-even point, compared to simpler methods, happens at a huge value of n (i.e number of bits in the multiplicands). Hardware, for example, tends to use O(n^2) methods because n is very small.

 

[Humus]

There are other considerations that are important too. Such as worst case scenario vs. the common case vs. best case scenario. For instance the quick sort algorithm, which is commonly used, has a best and common case of O(n log n), while it's worst case performance is O(n^2) (this is when the input list is sorted backwards) which is no better than bubble sort. In practice this method is very quick though unless you hit those slow special cases, so that's why it's commonly used.

Another consideration is if the method is supposed to be used multiple times and what average cost it has. For instance, a binary increment has O(1) steps, while the worst case is O. However, if you keep incrementing the number, the average number steps required is 2, as half the time you need just one step, in a 1/4 times you need 3 steps, 1/8 you need 4 steps and so on. The amortized cost, as it's called, is then O(1).

 

[Tim Murray]

oh god, reading this thread made me think I was twelve hours IN THE FUTURE...

(I have Fundamental Data Structures and Algorithms tomorrow. )

 

[Fred]

Big O, little o notation is basically programmers being very lazy. Lazier even than physicists (believe me thats hard to do).

For any given problem, the value that is important is....

the function f for some given domain.. Not O(f) which just in principle gives you the pallbark asymptotic behaviour as n --> infinity (or zero if you are working in inverse notation).

The idea is supposed to simplify your life, and it does in most cases, so you do not have to remember some complicated looking formula, but just the leading order terms. Well again, while it works in many easy cases, it is most certainly NOT guarenteed for all behaviour. Simon mentioned the cases where you might go very wrong for large (but not large enough) n.

There are other examples, for instance, where you have two leading terms that oscillate around one another --> infinity, in which case you *have* to specify a range for n and you have to be more careful. This happens in algorithms in lattice quantum chromodynamics. Believe me it makes a difference when the difference is on the order of the age of the universe, and we are looking for something more on the order O(1 month)

 

[DemoCoder]

Big-O notation is a tool of theoretical interest, just like complexity classes. It really has very little to do with programming in most cases, and more with computer science itself. You should still learn it, because algorithmic analysis is important, unless all you care about is taking existing algorithms and implementing them, rather than understanding how they work and investing your own.

 

[OpenGL guy]

I am a bit rusty on the whole o and O stuff, but I don't see why f = n^2 + f(n-1), f(0) = 0, would be O(n^3). Would you say g = n + g(n-1), g(0) = 0 is O(n^2)? I sure hope not as g = n + (n-1) + (n-2) + ... + 1 which is obviously no greater than O. If you're clever, then g = n(n+1)/2 which is O(1). Going back to the original problem, since f = n^2 + (n-1)^2 + ... + 1, I'd say that this is O(3n) = O as well as there are only n elements to compute, each being a square plus a sum.

If anyone here disagrees that f = n^2 is O(1) then I'll be very confused.

 

[DemoCoder]

It depends on how you view multiplication. The fastest known "practical" multiplication algorithm is nlogn (fast fourier transform + convolution + inverse transform). Karatsuba's method is n^lg(3)

So O(n^2) != O(1)

However, traditionally, you only count the cost of one kind of operation, not the individual arithmetic costs (e.g. cost of adds and mults), so you're essentially right.

Replace n^2 with any non-recursive polynomial of n and the result is still the same.

 

[OpenGL guy]

It depends on how you view multiplication. The fastest known "practical" multiplication algorithm is nlogn (fast fourier transform + convolution + inverse transform). Karatsuba's method is n^lg(3)

So O(n^2) != O(1)

I think you could have wrote that better but I know what you mean

However, traditionally, you only count the cost of one kind of operation, not the individual arithmetic costs (e.g. cost of adds and mults), so you're essentially right.

Replace n^2 with any non-recursive polynomial of n and the result is still the same.

Yes, that's exactly what I was referring to.