0

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
Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
Madeye Alastor Moody
  • 11
  • 5

1 Answers1

2

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.

Mark
  • 90,562
  • 7
  • 108
  • 148
  • “Big O notation considers the worst case scenario.” — Where does this come from? I keep seeing this on Stack Overflow, but the big O notation can of course also be used to analyse expected/average case behaviour (the expected runtime of generic quicksort is conventionally given as O(n·logn)), and in principle (though much rarer) even best-case behaviour. – Konrad Rudolph Jan 16 '22 at 17:34
  • That's a fair question @KonradRudolph. I think it's convention that when something like average case is not asked for we talk about the ceiling. For instance the best case in the above is constant time with a list that starts with an odd number, but that doesn't explain the complexity of the function. Average case is still O(n) (but that itself make assumptions about the distribution of input). On the other hand something like Quicksort is often described in terms of complexity of the average case, with a note the worst case is O(n2). – Mark Jan 16 '22 at 17:51
  • Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value. Computer science uses the Big O }, Big Theta Θ, and Big Omega notations to describe the Max, mean, and min performance see .[Introduction to Algorithms](https://en.wikipedia.org/wiki/Introduction_to_Algorithms) – itprorh66 Jan 16 '22 at 18:57
  • 1
    That's conflating two different things @itprorh66. The asymptotic complexity in the best or average case is not equivalent to Big Theta or Big Omega. There's a good discussion [here](https://stackoverflow.com/questions/39138236/is-theta-notation-called-the-average-case) – Mark Jan 16 '22 at 19:01
  • Big O is the upper bound, while Omega is the lower bound. Theta requires both Big O and Omega, so that's why it's referred to as a tight bound (it must be both the upper and lower bound). For example, an algorithm taking Omega(n log n) takes at least n log n time but has no upper limit. An algorithm taking Theta(n log n) is far preferential since it takes AT LEAST n log n (Omega n log n) and NO MORE THAN n log n (Big O n log n). – itprorh66 Jan 16 '22 at 19:07
  • That's great but that's not what we are talking about when comparing the best case (i.e. input like `[1, 2, 3]` which returns in constant time) and worst case `[2, 4, 6]` which is linear. If you think about it, defining Omega in terms of input would mean pretty much *all* algorithms would have Big Omega of constant time because you could always consider the empty input as the lower bound. That of course makes no sense and makes Big Omega meaningless. – Mark Jan 16 '22 at 19:24
  • 1
    With random numbers, average time is O(1). – Kelly Bundy Jan 16 '22 at 19:37
  • Yeah, that's an interesting insight @KellyBundy that I didn't consider in my first comment above. – Mark Jan 16 '22 at 19:52