CODEWITHSUNDEEP
time-complexitybig-o
rollo123
rollo123

Reputation: 25

Time complexity of for loop with if/else

Would the following code be considered O(1) or O(n)? The for loop has constant complexity which runs 10 times but I'm not sure whether the if condition would be considered O(n) or O(1).

for (i = 0; i < 10; i++)
{
if (arr [i] == 1001)
    {
        return i;
    }
}

Upvotes: 2

Views: 162

Answers (1)

dreamcrash
dreamcrash

Reputation: 51443

The complexity would be O(1), because regardless of how much you increase the input the complexity of the algorithm remains constant. Namely, the operations performed inside that loop are considered to have constant time, hence O(1).

for (i = 0; i < 10; i++)
{
    if (arr [i] == 1001) 
    {
        return i;
    }
}

On the other hand if your loop was:

for (i = 0; i < 10; i++)
{
    f(n)
}

and the function f(n) had a complexity of O(n) then the complexity of the entire code snippet would be O(n) since 10 * N can be labeled as O(n).

For a more in depth explanation have a look at What is a plain English explanation of “Big O” notation?

Upvotes: 1

Related Questions