CODEWITHSUNDEEP
timecomplexity-theory
Viking82
Viking82

Reputation: 11

Time Complexity of 3 nested for loops

Although, I found pretty good replies to the same question! However, I want time complexity equation of the following piece of code

sum = 0;                                            c1=11
for (i=0; i<N; i++)                                 c2=6
    for (j=0; j<N; j++)                             c2=6
        for (j=0; j<N; j++)                         c2=7
    sum += arr[i][j]                                c3=2

While each statement has a cost associated with it, I require complete time complexity equation and its answer.

Regards

Upvotes: 1

Views: 1631

Answers (1)

sinanspd
sinanspd

Reputation: 2734

The comments section got quite long so I am going to write up an answer summarizing everything.

Measuring Time Complexity

In Computer Science, we measure time complexity by the number of steps/iterations your algorithm takes to evaluate.

So if you have a simple array of length n and you go through this array only once, say to print all the elements, we say that this algorithm is O(n) because the time is takes to run will grow proportionally to the size of the array you have, thus n

You can think of Big-O O(..) as a higher order function that compares other functions. if we say f(x) = O(n) it means that you function grows at most as fast as y=n thus linearly. This means that if you were to plot these functions on a graph, there would be a point c x = c after which the graph of n will always be on top of f(x) for any given x > c. Big-O signifies upper bound of a function in terms of another function.

So let's look at your original question and what it means to be constant time. Say we have this function

def printFirst5(arr: Array[Int]) = {

     for(i =0 ;i < 5; i++){
         println(arr[i])
     }
 }

This is what we call a constant time algorithm. Can you see why? Because no matter what array you pass into this (as long as it has at least 5 elements), it will only go through the first 5 elements. You can pass it an array of length 100000000000 you can pass it an array of length 10 it doesn't matter. In each case it will only look at the first 5 elements. Meaning this function printFirst5 will never go above the line y=5 in terms of time complexity. These kind of functions are denoted O(1) for constant time.

Now, finally, let's look at you edited version. (I am not sure what you are trying to do in your example because it is syntactically wrong, so I will write my own example) 

    def groupAllBy3(array: Array[Int]) = {
       for(i=0; i < array.length; i++){
          for(j=0; j < array.length; j++){
            for(k=0; k< array.length; k++{
              println(s"$array[i], $array[j], $array[k]")
           }
         } 
       }
    }

This functions time complexity is O(N3). Why? Let's take a look.

The innermost loop will go through N elements for every j How many js are there? Well there will be N js for every i. How many is are there? N many.

So in total we get numberof-i * numberof-j * numberof-k = N * N * N = O(N^3)

Just to make sure you understand this correctly, let's take a look at another example. What would happen if these loops weren't nested? If we had:

    def printAllx3(array: Array[Int]) = {
       for(i=0; i < array.length; i++){
           println(s"array[i]")
       }

       for(j=0; j < array.length; j++){
           println(s"array[j]") 
       } 

       for(k=0; k< array.length; k++{
              println(s"array[k]")
        }
    }

What is the case here?

The first loop goes through N elements, the second loop goes through N elements, the third loop goes through N elements. But they don't depend on each other in terms of iterations so we get N + N + N = 3N = O(N)

Do you see the difference?

With all due respect, I believe you are missing some of the fundamentals of what time complexity is & how we measure it. There is only so much I can explain here, I highly recommend you do some reading on the subject and ask any further questions you don't understand.

Hope this helps

Upvotes: 1

Related Questions