[ragmar]

I'm not sure even to post this here, but no idea

for(int i = 0; i < 1; i++)
    for(int j = 0; j < 1; j++)
    a = i;

what is the big O of this fragment code.
i said it will be O(n²), but my teacher said it is O(n)

for(int i = 0; i < n*n; i++)
    for(int j = 0; j <= i; j++)
    a = i;

and for this one i said it is O(n³), but my teacher said it is O(n²)
is there any one who can help me understand that i am wrong, i can't admit it.
I just did it in an assumption that all arithmetic and logical operations will be computed once and for each nested loop there will be an extra n. Thanks in advance.

[Skydiver]

Moving to Computer Science...

[infernorthor]

Well the first code you have should be O(1) , unless it has a typo as that for loop would make no sense it just executes once
O(1) is like assignments , random access.

Ok so, I will try to explain how this is figured out.
A single for loop is easiest.
for(int i=0;i<n;i++)
this will be O(n).

for(int i=0;i<n*n;i++)
this will be O(n^2).

Now with double for loops you have to learn about series.

for(int i=0;i<n;i++){
    for(int j=0;j<i;j++){

    }
}

Now it should be obvious that inside loop will loop i times. So, {0,1,2,3,4,...,n}
Now to figure the total number of loops. You get the sum of series.
0+1+2+3+4+5+6+...+n this my adhoc sigma notation Sigma{i=0,n}(i)
This one happens to common which equals (n)(n+1)/2 = 1/2*n^2 + 1/2*n
So this code would be O(n^2)

now for

for(int i=0;i<n*n;i++){
    for(int j=0;j<i;j++){

    }
}

0+1+2+3+4+5+..+n^2
Using previous equation That would actually be 1/2*n^4 + 1/2*n^2 so O(n^4) based on n

[ragmar]

there are no typos in the first

for(int i = 0; i < 1; i++)
    for(int j = 0; j < 1; j++)
    a = i;

so the complexity for this is O(1), So weird.
i have my idea about time complexity from
is there any documentation about this so i can have better understanding with all the sigma stuff.

[infernorthor]

Well series is a whole field of math. There are plenty of sources like any math subject. Here's Wikipedia's to get you started.

I used to easily find a series table with pre-solved ones.

Determining O is basically how many statements are executed.

If you want to as a programmer test O(n^p) you could just do.

int count = 0;
for(..) {//some for's based on n
   for(..){
        count++;
   } 
}

After doing that count approximately will equal n^p

[ragmar]

for(int i=0;i<n*n;i++){
    for(int j=0;j<i;j++){
    }
}

for this code there is no way that is going to be O(n⁴).
As you have mentioned the first loop is n*n = n², and for the second loop since j = i and j is looping n^th times it will be n times.
So for the first loop times the second loop n² * n = n³.
i think i'm kinda sure but i might be wrong. Thanks in advance infernorthor.

[macosxnerd101]

infernorthor is correct- that segment of code is O(n⁴). The inner loop is O(k), where k = n². So by rule of product, we take the outer loop at O(n²) and multiply by the inner loop at O(k), which gives us O(n⁴).

We have a few good Complexity tutorials on DIC:
Mine on Deriving Runtime Functions and Big-O, Big-Omega, and Big-Theta

And KYA's on Big-O:
Part 1
Pat 2

[ragmar]

Thanks guys my bad the outer loop is n² and the inner loop is n²-1, which will be
n²(n²-1) = n⁴, i didn't see that the inner loop is n²-1 times the outer loop.

It might be stupid but is there a possible way that i can prove that my teacher was wrong and get my 3 mark back?
just hoping for one final recommendation before i print the page.

This post has been edited by ragmar: 25 September 2014 - 07:00 AM

[cfoley]

Well, your teacher got them both wrong so it's possible to prove him wrong. However, you got them both wrong too so no marks for you.

Edit: I should add that you won't care about the marks in 5 years time but maybe you might appreciate the understanding. So might your teacher and all his future pupils.

This post has been edited by cfoley: 25 September 2014 - 09:47 AM

[infernorthor]

ragmar, on 25 September 2014 - 07:53 AM, said:

Thanks guys my bad the outer loop is n² and the inner loop is n²-1, which will be
n²(n²-1) = n⁴, i didn't see that the inner loop is n²-1 times the outer loop.

It might be stupid but is there a possible way that i can prove that my teacher was wrong and get my 3 mark back?
just hoping for one final recommendation before i print the page.

It is not a matter of just multiply the loops, that would only work with particular instances, where the loops repeat statically(constant).

#define REPEAT(i,x) for(int i=0;i<x;i++)

\\ 5 * 2  = 10 = O(1)
REPEAT(i,5){
   REPEAT(j,2){
   }
}

\\ N * 3  = O(N)
REPEAT(i,N){
   REPEAT(j,3){
   }
}

\\ N * N = O(N^2)
REPEAT(i,N){
   REPEAT(j,N){
   }
}

\\ does not equal i*N not static must use series
REPEAT(i,N){
   REPEAT(j,i){
   }
}

[infernorthor]

I do see what you did to multiply the worst case of inner and outer together. But, that again maybe a specific math accident.
I would doubt that for all cases, unless there was a proof.

[ragmar]

\\ does not equal i*N not static must use series
REPEAT(i,N){
   REPEAT(j,i){
   }
}

Quote

does not equal i*N not static must use series

why i*N , the inner loop goes all the way where the outer loop goes, the outer loop goes N^th times
and the inner loop goes i^th times since the outer loop goes

for(int i=0;i<x;i++)

where i<x, the inner loop j<i, doesn't go like the outer loop it goes i-1 (only because it is < i, if it were <= it might be also like the outer loop) times from the outer loop.
BTW, no offense i'm not here to argue or proof i'm here to learn.

[infernorthor]

My point was that i*N doesn't make sense as i changes.

The inner loop doesn't go i-1, but i goes up to N-1 on the last loop.

In case that doesn't make sense.
The outer loop would go through this sequence the inner would loop the number in the sequence.
{0,1,2,3,4,5,...,N-1}

I guess my main point is that with

for(int i=0;i<n;i++)
{
   for(int j=0;j<i;j++){
   }
}

Doing (N)*(N-1) is multiplying the worst case, and doesn't actually equal T(n). And that (N)*(N-1) is just the upper bounds worst case so that (N)*(N-1) > T(N) from above. Now maybe I extrapolated too much from what you said, I just want you to understand how it works.
And also that even though in this case it does give you the correct Big-O but, that this method might not work for all nested for loops.

[macosxnerd101]

Let's derive the runtime function for this piece of code.

for(int i=0;i<n;i++)
{
   for(int j=0;j<i;j++){
   }
}

So the outer loop has a variable declaration and initialization, which is two steps. So we start with T(n) = 2. Then from i = 0 through n - 1, we evaluate a comparison (1 step) and an incrementation (2 steps) plus the inner loop. Let S(n) be the runtime function of the inner loop. So:

T(n) = 2 + \sum_{i=0}^{n-1} (3 + S(n))

Now let's derive S(n). So S(n) = 2 + \sum_{j=0}^{i-1} 3 = 2 + 3i. We have 2 steps for the variable declaration and initialization, and then 3 steps on each iteration (comparison and incrementation).

So T(n) = 2 + \sum_{i=0}^{n-1} (3 + \sum_{j=0}^{i-1} (2 + 3i)) = 2 + 3n + \sum_{i=0}^{n-1} (2i + 3\sum_{j=0}^{i-1} i) = 2 + 3n + n(n-1) + 3 * n(n-1)/2.

And so T \in O(n²).

*Note- it's early and I'm liable to have made a minor algebra error, but the n(n-1) terms should be there. As those are the dominant terms, you have quadratic time.