SaiKiran - 5 months ago 16

C Question

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

}

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";

}

`for(int i = 0; i < len(array); i+=2){`

if(key == array[i])

cout<<"Element found";

}

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

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

.