SaiKiran - 1 month ago 5
C Question

# Is a loop that is running a constant number of times considered Big - Oh(1)?

From a popular definition ,a loop or recursion that runs a constant number of times is also considered as O(1).

For example the following loop is O(1)

``````// Here c is a constant
for (int i = 1; i <= c; i++) {
// some O(1) expressions
}
``````

Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount.

For example following functions have O(n) time complexity.

``````// Here c is a positive integer constant
for (int i = 1; i <= n; i += c) {
// some O(1) expressions
}
``````

I got a little confused with the following example here lets take c = 5 and according to the O(1) definition the below code becomes - O(1)

``````for(int i = 0; i < 5 ; i++){
cout<<"Hello<<endl";
}
``````

## Function 1:

``````for(int i = 0; i < len(array); i+=2){
if(key == array[i])
cout<<"Element found";
}
``````

## Function 2:

``````for(int i =0;i < len(array) ; i++){
if(key == array[i])
cout<<"Element found";
}
``````

But when we compare the above 2 examples will they both become O(n) or first function is O(1) from definition.What exaclty does a loop running constant number of times means?

Assuming that `len(array)` is the `b` we're talking about [*], both your functions are `O(n)`.
Function 2 will execute the `if` n times (once for each element of the array), making it obviously `O(n)`.
Function 1, on the other hand, will execute the `if` `n/2` times (once for every other element in the array), leading to a run time of `O(n*1/2)`, and since constant factors (`1/2` in this case) are usually omitted in O notation, you'll again end up with `O(n)`.
[*] For the sake of completeness, if your array were of a fixed size, ie. `len(array)` were a constant, than both functions would be `O(1)`.