CODEWITHSUNDEEP
javascriptalgorithmtime-complexity
Ye Shiqing
Ye Shiqing

Reputation: 1669

A puzzle about time complexity calculation and real time consumption

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

Upvotes: 0

Views: 172

Answers (2)

user2736738
user2736738

Reputation: 30936

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).

Upvotes: 3

E. Villiger
E. Villiger

Reputation: 916

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.

Upvotes: 0

Related Questions