I had no idea! How come I had to be this old to learn this (despite having a bachelor degree in Mathematics)!
Small series:
>>> 1+2+3+4+5
15
>>> sum(range(5)
15
>>> 5*(5-1)//2
15
and larger
>>> 1+2+3+4+5+6+7+8+9+10+12+13+14+15
109
>>> sum(range(15))
105
>>> 15*(15-1)//2
105
and super large
>>> sum(range(100_000_000))
4999999950000000
>>> 100_000_000*(100_000_000-1)//2
4999999950000000
The sum function is O(n) and the multiplication is O(1).
To "prove" that, using speed, you can use:
>>> from time import perf_counter
>>> def T(func):
... t0=perf_counter(); func(); t1=perf_counter(); print((t1-t0)*1000,"ms")
>>> T(lambda: sum(range(100_000_000)))
680.1022500148974 ms
>>> T(lambda: 100_000_000*(100_000_000-1)//2)
0.001374981366097927 ms
Comments