I am trying to understnad if the following codes have the same complexity O(n)?:
for(int i=0;i<n;i++)
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
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:
As another exercise, let's compare
for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { body(); } }
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.
So both are O(n2)