SaiKiran SaiKiran - 2 months ago 6
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?

Answer

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