running time of for loop that executes only once

Question

Given-

m=1,k=1
for(i=1,.....,k){
  for(j=1,....,i){
     m=m+1;
}
}

Well, this is going to execute no more than 1 time. I guess the running time is theta(1). am I wrong??

Any code related to your question should be in the question itself. Don't make folks access external resources. Also, code should be text, not an image. — hatchet - done with SOverflow, Mar 17 '17 at 22:28
i m new here... the attached image doesn't seem to be appear automatically — akash, Mar 17 '17 at 22:29
I don't think you should be considering time complexity of a single instance (k=1). It should be the time complexity of the function as the size of the input increases (k in your case). — hatchet - done with SOverflow, Mar 17 '17 at 22:45

score 0 · Accepted Answer · edited May 23 '17 at 12:17

I don't think you should be considering time complexity of a single instance (k=1). It should be the time complexity of the function as the size of the input increases (k in your case).

If we take your question as it is though, then you are right as described here.

However, finding the minimal value in an unordered array is not a constant time operation as a scan over each element in the array is needed in order to determine the minimal value. Hence it is a linear time operation, taking O(n) time. If the number of elements is known in advance and does not change, however, such an algorithm can still be said to run in constant time.

In essence, that's what you seem to be asking. The size of the input (k) is known in advance (1) and does not change, so it is constant time, as presented.

If you consider that k can change then it's a different question. For that, I refer you to this question on stackoverflow for Time Complexity of nested for loop.

running time of for loop that executes only once

1 Answers1