CODEWITHSUNDEEP
algorithmcomplexity-theorybig-o
CBreeze
CBreeze

Reputation: 2973

Program complexity classes

Basically I am struggling to come to grips with operation counting and Big-O notation. I understand it is possibly one of the harder parts of computer science to understand and I have to admit I am struggling with it. Could anyone give me some help with these examples, and possibly any further help/links with Big-O?

for (i = 0; i < N; i++)
     { for (j = i; j < N; j++)
          { sequence of statements }
     }

Here I would say the complexity is O(N²) - Quadratic

int m = -9
for (j = 0; j < n; j+=5)
     {
     if (j<m)
          {
          for (k = 1; k <n; k*=3)
               {some code}
               }
     }

Here I would also say is O(N²). The first loop takes N and the second loop takes N so I would say the answer is O(N*N) which is equal to O(N²).

Any help and advice for further understanding would be great!!

Upvotes: 0

Views: 112

Answers (5)

Aman Chhabra
Aman Chhabra

Reputation: 627

Ok, also on a further note I would really suggest you to go through a single lecture in the series of introduction of algorithms. Believe me you won't need to look any further. http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

Upvotes: 0

JoshG79
JoshG79

Reputation: 1687

Just to throw this out here: if we assume that the j<-9 clause is a mistake and ignore it, then your second example has two nested loops. However the inner loop is actually multiplying k times 3. So this makes this inner loop O(log n). Which makes the pair of loops O(n log n). I'm not sure this is the answer, but you asked for further understanding, so... you know... maybe that's further.

Upvotes: 0

Bal&#225;zs Sz&#225;nt&#243;
Bal&#225;zs Sz&#225;nt&#243;

Reputation: 1500

First example: The inner loop executes N times when i = 0, N-1 times when i = 1, and so on... You can just calculate the number of steps the for loops execute

(N) + (N - 1) + (N - 2) + ... + 2 + 1

steps = N(N+1)/2 = (N^2 + N) / 2

  1. N <=> 1 |add the left to the right| => N+1
  2. (N - 1) <=> 2 |add the left to the right| => N+1
  3. (N - 2) <=> 3 |add the left to the right| => N+1 . . . N

What does the big-O nation means?

F(N) = O(G(N)) means that |F(N)|<= c*|G(N)| where c > 0

It means that the G(N) function is an upper bound on the grothw rate of the function. F(N) could not grow faster than G(N).

Upvotes: 0

John
John

Reputation: 16007

The second example is complexity O(N).

int m = -9
for (j = 0; j < n; j+=5)
{
    if (j<m)
    {
        // this never executes; m is negative and j is positive
    }
}

Upvotes: 1

amit
amit

Reputation: 178481

The first is indeed O(n^2), as you suspected, assuming the 'sequence of statements' is O(1).

However, the second part of code is O(n), since the condition j < m is never met - and thus, the outer loop only iterates itself without actually doing nothing. The inner loop is not even reachable.

As side note, some compilers may actually optimize the second part of code to run in O(1) by just setting the end values of variables, but this is not the point of the question.

Upvotes: 2

Related Questions