ccomplexity-theory

Is a loop i<n has the same complexity as i<100?


I am trying to understnad if the following codes have the same complexity O(n)?:

  1. for(int i=0;i<n;i++)

  2. for(int i=0;i<100000;i++)

i would be happy to hear an explanation too, thank you !

I think that the second loop's complexity is O(n) since in the worst case senario , we run through all the numbers, but my teacher said it's complexity is O(1) and I dont know why


Solution

  • Complexity is a measure of how the usage of a resource (CPU time, memory, etc) scales as a variable increases.

    The following can be said of the CPU time in terms of n:

    1. The CPU time used increases (at most) linearly with n, so it's O(n).
    2. The CPU time used doesn't increase with n, so it's O(1).

    As another exercise, let's compare

    1. for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { body(); } }
    2. for(int i=0;i<n;i++) { for(int j=i;j<n;j++) { body(); } }

    Let's count the number of times body is called.

    1. n2 times.
    2. n+...+3+2+1 = n(n+1)/2 = ½n2 + ½n

    So both are O(n2)