big O notation

[saiz66]

Hi. I learned the big O notation in class, but I still don't understand it. I have a test coming up and I was wondering if anybody could tell me how it is done. I have examples which my teacher gave us to practice on. I will post a few here and please could you tell me what I have to do and any tips and tricks?

a) for(j =0; j<=n, j+=2)

printf("Hello\n");

for (k=n-1; k>1; k-=3)

printf("Good Bye\n");

c) for(i=1; i<=n; i+=3)

for(j=i; i<= i+5; ++i)

sum++;

for(k=n; k>=0; --k)

printf("Result = %d\n", sum-k);

[b0nk]

Big O notation represents the max number of iterations(not really the word I want to use) of an algorithm.

For example if you have a program that just printed everything in an array it would be:

"On" because you are going though everything once

If you had a selection sort algorithm it would be:

"On^2" because of the nested for loops.

This is a pretty bad explanation... use google.

I think the two alogorithms you have there are both "On" because they both are linear. However, I could be wrong.

Edited June 16, 2004 by b0nk

[pballsim]

a:

O(n/2) + O(n / 3)

=> O(n) + O(n)

=> O(2n)

=> O(n)

b.

O(n/3)*O(n/5)+O(n)

=> O(n)*O(n) + O(n)

=> O(n^2) + O(n)

=> O(n^2)

[saiz66]

thanks bonk. I understand the point of big o notation and what you have said. But I don't understand the more complex examples such as using the summation notations for quadratic loops and dependent quadratic loops. I googled but I could not find a detailed tutorial on it, just the basics which I already know.

[saiz66]

pballsim thanks for the reply, could you explain how you got those? I still don't really understand. Also could you tell me how to do while loops?

b) i = n

while (i>0)

{

pirntf("Fun Times\n'");

i/=2;

}

d)

i = 2;

while (i < n)

{

for (j=i; j> 0; --j)

printf(%d\n",i);

i++;

}

Thanks!

}

[pballsim]

It helps I taught this in college =)

It depends on your indexing.

If you are ADDING or SUBTRACTING the same value (m) to your index (i) your notation will be: O(i / m)

If you are MULTIPLING or DIVIDING the same value (m) to your index (i) the notation will be: O(log(i, base m))

So:

b) i = n

while (i>0)

{

pirntf("Fun Times\n'");

i/=2;

}

will end up being:

log ( n ) - log is usually base 2 in computer science but you should specify it.

The other way I tell people is to write out iterations; For the while loop you will have:

n | i

0 |

1 | 1

2 | 2 1

3 | 3 1

4 | 4 2 1

5 | 5 2 1

6 | 6 3 1

7 | 7 3 1

8 | 8 4 2 1

Notice how you add a new digit every power of 2 - if you keep doing this you will get a logrithmetic graph.

[eversor]

My guess would be:

b) O(log(n))

d) O(n!)

Its somehow hard to explain. But is has less to do which loop you deal with but what you do with the variables in the loop.

Edit: Ah. I see pballsim took his time to explain this. Good explanation! I suck at explaining this kinda stuff because i don't exactly know how i do it myself. I just see it somehow...

[b0nk]

Just from looking at it I can see how "B" would be OLog(n) because i is being cut in half.

[pballsim]

d is actually O(n^2) since the while loop is only incrementing the index i.

[OPaul]

The first one looks like O(n) to me, there's no nesting going on.

[Jason S. Global Moderator]

man... i thought for sure someone would post something sexual by now... like "why dont you practice your big O on your teacher" or something ;)

[saiz66]

thanks a lot! I have learned somewhere to use summation notations. Could you teach me how to use summation notations? I have an example in my lecture notes on dependent quadratic, but I dont really understand how to use it.

i = 1;

loop(i <=10)

j=1

loop(j<=i)

application code

j=j+1;

end loop

i=i+1;

endloop

the answer it says is n(n+1)/2 but i dont understand how they got this.

[bwx]

http://www.me.berkeley.edu/~e77/lecnotes/ch20/ch20.htm

I found this quite helpful...

bwx

[pballsim]

Big O notation you ignore contants... so everybody will give you O(n^2)

But the reason they get that is the loop goes as follows how it's adding the numbers. It's essentially adding 1, then 1 2, then 1 2 3, and based off of Gauss's formula for adding:

1 2 3 4 ... n

efficiently is: n(n+1) / 2

[saiz66]

oh ok.. but how do i know when to use summation notations?

[saiz66]

also, are while loops always O(log n) ?

[Original_]

also, are while loops always O(log n) ?

No.

Take a look @ QuickSort.

[ThunderRiver]

Hehe I was confused on Big O Big Omega Big yada yada when I was taking discrete math class. It was one of the worst class I ever taken. The concept is easy, and yet there is a "definite" answer for each type of problem.

I bailed out that class the first time also because my prof doesn't speak English well at all. I tried it the second time, and got a B- in that class (Odd enough, my prof encuraged me to quit.. wow the first time eh?). Still that Big O concept has always been rough to me. There is no good textbook out there that make your life easier either.

Pretty much after that class, I quit CS major. Now that i look back, I haven't regret yet.

So yeah, that's what happened to me at University of Michigan Ann Arbor (PS don't go there if you are out of state, you won't get much financial aids.)

Edited June 17, 2004 by ThunderRiver

[pballsim]

You have to look at how the variables are. See my previous post. If your indexing is increasing/decreasing by a constant in any kind of loop then it's O(n/constant).

A for loop is not always O(n). E.g.

for (int i = n; i > 0; i /= 2)

this is an O(log(n))

A for loop, while loop and do while loops are exactly identilcal and can be written using one another. A for loop is just syntax sugar for:

void foo()
{
 ? // ...
 ?{
 ? ? int i = n;
 ? ? while (i > 0)
 ? ?{
 ? ? ? ?i /= 2;
 ? ?}
 ? ?// ...
}

Except if you don't use the { before the int i then you can use 'i' after the loop. But in a for loop you cannot use i after you declare it. You would have to declare it before you define your for loop.

[incubusdaemon]

http://www.me.berkeley.edu/~e77/lecnotes/ch20/ch20.htm

I found this quite helpful...

bwx

Hey, I took that exact class! (I go to berkeley) Such a waste of a semester. Let me find the notes for the CS class on the same topic.

http://www.cs.berkeley.edu/~jrs/61b/lec/20

edit: if you have a postscript reader, this will have better graphs: http://www.cs.berkeley.edu/~jrs/61b/lec/20.ps

(they are a lot more formal, but if you understand the formalities, it's a lot easier in practice.)

[saiz66]

So to understand this Big O thing, I only have to know this:

"It depends on your indexing.

If you are ADDING or SUBTRACTING the same value (m) to your index (i) your notation will be: O(i / m)

If you are MULTIPLING or DIVIDING the same value (m) to your index (i) the notation will be: O(log(i, base m))"?

I only have to look at indexing right?