2

I'm having some trouble fully understanding Big-O notation and how nested loops impact the running time. I know time complexity of nested loops is equal to the number of times the innermost statement is executed but I just want to check my understanding.

1

count=1
for i=1 to N
    for j=1 to N
        for k=1 to N
            count+=1

Since there are 2 nested loops, it would be O(N3), correct?

2

count=1
for i=1 to N^2
    for j=1 to N
        count+=1

The outer loop iterates N2 and inner loops runs N times which makes it O(N3), right?

3

count=1
for (i=0;i<N;++i)
    for (j=0;j<i*i;++j)
        for (k=0;k<j;++k)
            ++count

This would be O(N) right since N is only being called in the first for loop?

Community
  • 1
  • 1
S. Schmidt
  • 21
  • 2
  • 2
    In the third case, it is n^4, even if n is only "called" once, j is referring to i, and k is referring to j. – user1470500 Sep 21 '17 at 12:42
  • 1
    Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Paul Hankin Sep 21 '17 at 12:55
  • This will help you understand [**Big O**](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation?rq=1) Better. Also the time complexity for the third example is **`O(N^4)`** – Ishpreet Sep 21 '17 at 18:09

1 Answers1

-2

The Big O -notation describes how the algorithm or program scales in performance (running time, memory requirement, etc.) with regard to the amount of input.

For example:

  • O(1) says it will take constant time no matter the amount of data
  • O(N) scales linearily: give it five times the input and it will take five times a long to complete
  • O(N^2) scales quadratically: e.g. ten times the input will take a hundred times as long to complete

Your third example is O(N^4), because that is how the the total number of innermost iterations scale for N.

For these simple cases you can count the innermost number of iterations, but there are certainly more complicated algorithms than that.

krisku
  • 3,916
  • 1
  • 18
  • 10