[Solved] What will be the big-O notation for this code?

by


The way I see it, your code would be O(n) if it wasn’t for the a.pop(0) part. Since lists are implemented as arrays in memory, removing an element at the top means that all elements in the array need to moved as well. So removing from a list is O(n). You do that in a loop over j and as far as I can tell, in the end, the sum of all js will be the same as n, so you are removing the item n times from the list, making this part quadratic (O(n²)).

You can avoid this though by not modifying your list, and just keeping track of the initial index. This not only removes the need for the pop, but also the loop over j, making the complexity calculation a bit more straight-forward:

final_count = 0
offset = 0
while n > 1:
    i = 0
    j = 1
    while a[offset + i + 1] == a[offset + i]:
        i += 1
        j += 1
        if i == n - 1:
            break

    offset += j
    final_count += j * (n - j)
    n = n - j

Btw. it’s not exactly clear to me why you keep track of j, since j = i + 1 at every time, so you can get rid of that, making the code a bit simpler. And at the very end j * (n - j) is exactly j * n if you first adjust n:

final_count = 0
offset = 0
while n > 1:
    i = 0
    while a[offset + i + 1] == a[offset + i]:
        i += 1
        if i == n - 1:
            break

    offset += i + 1
    n = n - (i + 1)
    final_count += (i + 1) * n

One final note: As you may notice, offset is now counting from zero to the length of your list, while n is doing the reverse, counting from the length of your list to zero. You could probably combine this, so you don’t need both.

1

solved What will be the big-O notation for this code?