CODEWITHSUNDEEP
pythonpython-3.x
jacobcan118
jacobcan118

Reputation: 9099

how to calculate Big O with while + for loop

I got the following code and was told that Big O for the func function is Big O (n^ 2). I believe it is Big O(n) since it is should Big O(n + n), am I wrong?

what is Big O of following func?
nums = list(range(1, 11))
K = 4
def func(nums: list, K:int):         
    i, end = 0, len(nums)         
    res = []         
    x = []         
    while i < end:             
        res.append(nums[i:i+K])             
        i += K         
    for i in res:
        x += i[::-1]
    return x
func(nums, K)

Upvotes: 1

Views: 98

Answers (2)

philszalay
philszalay

Reputation: 433

In fact the Big O for this function is O(n). Assuming that the code is properly formatted.

The loop over res still has a linear runtime. There is no case where enough elements are added to res in the first loop so that the second loop has a Big O of O(n^2).

Upvotes: 0

ritlew
ritlew

Reputation: 1682

The function would be O(n). The first while loop iterates less than n times because its upper bound is n (end), and the counter increments by more than 1 every iteration.

The for loop iterates over res, which is a subset of nums. Since it is a subset, it will not iterate more than n times, making it O(n).

O(n) + O(n) = O(n), so your assessment is correct.

Upvotes: 1

Related Questions