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

Question

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

Answer 1

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. n² times.
2. n+...+3+2+1 = n(n+1)/2 = ½n² + ½n

So both are O(n²)