Jan-18-2017, 09:32 PM
Thanks for the plug, Mek.
@wavic:
To dig into it a bit more, the code
Given, f(x)=x*x/2, doubling x results in a more than doubling of f(x), as shown below
f(2) = 2
f(4) = 8
f(8) = 32
The reason Mek's solution is O(n) is that within the loop (which runs n times), only constant-time operations are taken. Operating on a dictionary is efficient (O(1)) so long as you're not doing other linear operations, like collection.count().
@wavic:
To dig into it a bit more, the code
for s, i in enumerate(l, 1):
l[:s]is quadratic (O(n**2)) because slicing is a linear operation. During the first iteration, n work is done, during the second is (n-1) etc. down to 1. On average, n/2 work is done within the loop, but the halving doesn't matter.Given, f(x)=x*x/2, doubling x results in a more than doubling of f(x), as shown below
f(2) = 2
f(4) = 8
f(8) = 32
The reason Mek's solution is O(n) is that within the loop (which runs n times), only constant-time operations are taken. Operating on a dictionary is efficient (O(1)) so long as you're not doing other linear operations, like collection.count().