1

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)
D.Morrissey
  • 114
  • 8
jacobcan118
  • 7,797
  • 12
  • 50
  • 95

2 Answers2

1

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.

ritlew
  • 1,622
  • 11
  • 13
0

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

philszalay
  • 423
  • 1
  • 3
  • 9
  • 1
    That isn't true. You could append the entire list `nums` to `res` `n` times, making the for loop O(n^2) – ritlew Apr 04 '19 at 15:00
  • I feel that your answer is still misleading – ritlew Apr 04 '19 at 15:03
  • still do not understand, even when K is size of nums, while will only run once and for loop run once + python reverse Big O(n)..how it turns into n ^ 2? – jacobcan118 Apr 04 '19 at 15:40
  • @jacobcan118 https://stackoverflow.com/a/13203617/10813463 substring slice is O(sizeof(slice)). In this case, O(K+i - i), O(K). It is, however, a bit confusing since as K gets larger, you loop through less times in the while loop but more in the string. I'm not sure how to assess that. – Nick Vitha Apr 04 '19 at 15:48
  • Your answer slightly sounds like "because it is a for loop (as opposed to nested), it will always be O(n)" – ritlew Apr 04 '19 at 15:52