What does O(n) and O(k) mean?

Question

I have this task:

Given an array of integers and a number k, where 1 <= k <= length of the array, compute the maximum values of each subarray of length k. For example, given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get: [10, 7, 8, 8], since:

10 = max(10, 5, 2)
7 = max(5, 2, 7)
8 = max(2, 7, 8)
8 = max(7, 8, 7)

Do this in O(n) time and O(k) space. You can modify the input array in-place and you do not need to store the results. You can simply print them out as you compute them.

What does O(n) time and O(k) space mean?

I got this solution. Does this fulfill the requirements? If not, why not?

def foo(arr, k):
    for idx in range(0, len(arr) - k + 1):
        maxI = -1
        for i in arr[idx:idx + k]:
            if i > maxI:
                maxI = i

        print(maxI) #3; 3; 3; 5; 5; 5; 10; 22

arr = [0, 1, 3, 1, 2, 5, 5, 4, 10, 22]
k = 3

foo(arr, k)

Does this answer your question? [What is a plain English explanation of "Big O" notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) — MoonMist, Dec 10 '19 at 22:30
I'm still not quite sure if this code above is O(n) or O(n^2) time? What about O(k) space? — IceRevenge, Dec 10 '19 at 22:38
It works in O(k) space and O((n - k + 1) · k) time, which doesn’t meet the requirements, no. (Selecting k proportional to n plus a few other restrictions makes it O(n²), for example.) — Ry-, Dec 10 '19 at 22:42
@Ry- but O((n - k + 1)*k) = O(n*k - k^2 + k). Since we only care about n at time, k is seen as constant so it isn't important for the calculation so O would be seen as O(n) right? — IceRevenge, Dec 10 '19 at 22:46
To your edited version, what if you see k as 3... then it would be O(n). Which one do you choose then? Is this where the worst case thing from the answer from the linked question above comes in? — IceRevenge, Dec 10 '19 at 22:47
@IceRevenge: There should be a constant that you could choose so that the algorithm is O(n) no matter which k. — jxh, Dec 10 '19 at 22:48
@IceRevenge: We don’t only care about n. A lot of the time, k is used as the name of a constant, which is a bit misleading, but here it can be chosen anywhere from 1 to n. (Probably. You would have to ask whoever asked you the problem to be sure of what’s expected.) — Ry-, Dec 10 '19 at 22:49
@Ry- ok thanks. I think that was my problem with understanding it... — IceRevenge, Dec 10 '19 at 22:52

jxh · Answer 1 · 2019-12-10T22:56:42.267

0

I would take n to represent length of the array, and k to represent length of the subarray.

Ο(n) time would be that the time taken by the algorithm would be proportional to the length of the array. I.e., the running time for an array of length 1000 would be half as the running time for an array of length 2000.

Ο(k) space would be the amount of memory needed by the algorithm to perform the computation is proportional to the size of the subarray. Stated in this way, it is independent of the size of the input.

Your algorithm makes n - k + 1 iterations over a loop that makes k iterations. This makes its execution time on the order of k × (n - k + 1). Since k can vary with n, the average case should be taken to be k = n/2, giving you a runtime of Ο(n²).

The space taken by your algorithm is Ο(1), since you only need a few integer variables.

edited Dec 10 '19 at 22:56

answered Dec 10 '19 at 22:39

jxh

69,070
8
110
193

Ok... so since the inner loop is dependent on the length of k (which is then seen as a constant term right?), the entire code runs at O(n) time, doesn't it? – IceRevenge Dec 10 '19 at 22:43
One way to infer the running time complexity of your algorithm is to implement it, and then execute it against varying sized inputs, and then plot the execution time against the input size and see what the graph looks like. – jxh Dec 10 '19 at 22:45

What does O(n) and O(k) mean?

1 Answers1