0

While learning the basic knowledge of algorithm, I find puzzle about the time complexity calculation and the real time consumption when run the codes.

The demo codes specify the problem.

function calcDemo1(){
    var init = 0; 
    for(var i=0;i<40;i++){
        init += 0;
    }
    return init;
}

function calcDemo2(){
    var init = 0; 
    init += (0+1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39);
    return init;
}
  1. Does calcDemo1's time complexity is O(1) even if it's a "for loop"?
  2. In case their time complexity were both O(1), do they take the same amount of time in the worst-case scenario when run the code?

The relative question is here

Brian Tompsett - 汤莱恩
  • 5,753
  • 72
  • 57
  • 129
Ye Shiqing
  • 1,519
  • 2
  • 15
  • 24
  • 2
    The second part of your question is impossible to answer. With the highest probability, the two snippets will take different amounts of time. Heck, if you even rerun the same function, it will most probably take a different amount of time due to your javascript engine, browser, operating system, ... having to also solve different problems in pseudo-concurrent way. If you need to know how much it takes on your specific computer at a specific instant in this universe, feel free to run it, but don't expect it to be reproducible. – Zdeněk Jelínek Nov 14 '17 at 09:25

2 Answers2

3

Both of them have constant time complexity. O(1) time complexity.

For case-1 there is an for loop but it runs 40 times. So it will be of constant time complexity.

In the second case, no for loop is there, but it is still contant time addition. So it is O(1) again.

It doesn't mean that if there is for loop it's complexity can't be constant.

As reply to the comment, yes even if we increase the hardcoded value then the time complexity won't change. It will be still O(1).

user2736738
  • 30,591
  • 5
  • 42
  • 56
  • Complexity is always in reference to a certain algorithm. Now, if the number 40 is hard-coded into the algorithm, then, yes, it will be constant time complexity because there is no change in input. I'm pretty sure, though, that the OP wants to know the time complexity for varying inputs (say 1000 instead of 40) – E. Villiger Nov 14 '17 at 09:14
  • @E.Villiger.: I replied in answer. – user2736738 Nov 14 '17 at 09:17
  • 1
    You are right that if the hardcoded value is constant, then the time complexity is constant. Usually with these types of questions, though, it's wondering how the algorithm performs for **varying** input sizes. – E. Villiger Nov 14 '17 at 09:19
  • 1
    @E.Villiger.: If the loop depends on the input size then yes a for loop over range [1,n] will yield O(n) time complexity given that what we do inside loop is constant in time. – user2736738 Nov 14 '17 at 09:20
0

Constant time complexity O(1) means that the execution takes the same amount of time, no matter how big the input.

Linear time complexity O(n) means that execution takes longer to the same degree that the input size increases.

Your examples

It depends on what you define as your input. In my analysis below I am assuming that your input is the number of times to loop/add a number (40). If there is no input at all, then any code will just be of constant time complexity O(1).

calcDemo1 most likely has linear complexity because the javascript compiler isn't smart enough to figure out that it could just skip the loop. It will actually increase i 40 times and then add 0 to init 40 times (or at least check if it actually has to add anything). Therefore, each rotation of the loop actually takes some time and, say, looping 4000 times would 100 times longer than 40 times.

calcDemo2 also has linear complexity O(n): Adding 1 million numbers should take roughly 1000 times as long as just adding 1000 numbers.

E. Villiger
  • 876
  • 10
  • 27
  • As u say, the time consumption increase since the input size increasing. Why doesn't it influence the time complexity? Does it due to the specification of the time complexity calculation? – Ye Shiqing Nov 14 '17 at 10:49
  • I'm not sure what you're asking. Time complexity only describes the general shape of a time consumption vs. input size graph. In other words, time complexity itself doesn't give you any information on how long something might take, it only tells you how long it would take compared to running the same problem with a different input size. – E. Villiger Nov 14 '17 at 11:24