CODEWITHSUNDEEP
pythontime-complexity
Madeye Alastor Moody
Madeye Alastor Moody

Reputation: 11

Find runtime (number of operations of function) and calculate Big O

For the python function given below, I have to find the number of Operations and Big O.

def no_odd_number(list_nums):
    i = 0
    while i < len(list_nums):
        num = list_nums[i]
        if num % 2 != 0:
            return False
        i += 1
    return True

From my calculation, the number of operations is 4 + 3n but I'm not sure as I don't know how to deal with if...else statements.

I am also given options to choose the correct Big O from, from my calculation, I think it should be d. O(n) but I'm not sure. Help please!

a. O(n^2)

b. O(1)

c. O(log n)

d. O(n)

e. None of these

Upvotes: 0

Views: 433

Answers (1)

Mark
Mark

Reputation: 92440

Big O notation typically considers the worst case scenario. The function you have is pretty simple, but the early return seems to complicate things. However, since we care about the worst case you can ignore the if block. The worst case will be one where you don't return early. It would be a list like [2,4,6,8], which would run the loop four times.

Now, look at the things inside the while loop, with the above in mind. It doesn't matter how big list_nums is: inside the loop you just increment i and lookup something in a list. Both of those are constant time operations that are the same regardless of how large list_nums is.

The number of times you do this loop is the length of list_nums. This means as list_nums grows, the number of operations grows at the same rate. That makes this O(n) as you suspect.

Upvotes: 2

Related Questions