sum series and time complexity — kitallis.in
sum series and time complexity
May 26, 2026
My highly sophisticated rule of thumb for eyeballing time complexity is to find the cheapest unit of work and count how many times it runs. I find it a bit more reliable than counting the nested loops. This is easy to see why:<br>left = 0<br>(0...n).each do |right|<br>while bad<br>left += 1<br>end<br>end<br>Here, right and left only move forward once , so the total amount of movement is 2n, linear time.<br>Similarly, a nested loop that doubles against the cut off internally:<br>(1...n).each do |i|<br>j = i<br>while j The outer loop runs n times (from 1 to n-1) and the inner loop runs possibly n times. But not really, the inner loop j doubles with respect to i. The number of times it doubles goes like this:<br>i→ 2i→ 4i→ 8i→ nRepeated doubling (or halving) that reaches n is logarithmic, so you get an inequality like this:<br>2k × i n<br>2k ni<br>k log ( ni )<br>So for every i, log(ni) is the number of operations. For all i, it's ∑log(ni), since we're just counting the operations (k), not the actual value (that's what the program is for!)<br>∑ i=1 n log ( ni ) = n·log(n) − log(n!) ≈ n<br>∑log(ni) reduces down to O(n) after applying Stirling's approximation. The derivation of how that happens is less interesting than the fact that knowing your series summations can be pretty useful in intuiting how time complexity analyses (tricky ones especially) work.<br>In both examples, it might appear (if poorly analysed) that these algorithms are quadratic, but they aren't.
This got me attempting a rather tricky one, even though I tacitly know this is something like O(loglogn), I was having a hard time understanding why:<br>i = n<br>while i > 2<br>i = Math.sqrt(i)<br>end<br>After some dubious scratch math, I managed to arrive at a no-prior-inspiration analysis. The only prior is the definition of logarithm itself 2x=n, x = log2(n). Or more generally, Bx=n, x = logB(n), where B is the base.<br>In the code above, we start with n and repeatedly take square roots. Square roots are simply fractional powers, n12.<br>The loop runs until we hit just over 2. Let's say it runs k times (since we don't really know yet, by just looking at it). It goes like this, for n=65536, it'd be k=4:<br>iterationvalueis also(216)12256→ 28(28)1216→ 24(24)124→ 22(22)122→ 21(21)121→ In other words, we're doing,<br>iterationvalueis also(216)12256→ 28(216)1416→ 24(216)184→ 22(216)1162→ 21(216)1321→ This is just, (n)12k where, n=216 (our original starting number). We're reducing the fractional exponent k times to arrive roughly above 2, our target cut-off point. The point of writing the reduction in the form of a fixed 216 is so we can treat the expression as n, because that's the input size that we'll measure the time complexity against. k is what we're solving for, not its value at any particular n, but how it grows as n does.<br>So it'd be fair to say that our loop represents this inequality:<br>n 1 2k > cut_off<br>or, in powers of two (so we're working against same-base logs),<br>( 2 m ) 1 2 k > cut_off<br>We need to solve for k, but it's stuck as a non-trivial exponent on top, but since 2x=n, x = log2(n), we can use that to pull it down:<br>m 2k > log2(cut_off)<br>m > 2k · log2(cut_off)<br>m log2(cut_off) > 2k<br>2k m log2(cut_off)<br>k log2 ( m log2(cut_off) )<br>since, 2m=n, m = log2(n)<br>k log2 ( log2(n) log2(cut_off) )<br>Since log2(cut_off) is constant, we get O(loglogn)... and that's that. Doubling (or halving) to a cutoff is log(n), doing it to the exponent is log(log(n)): a quick rule of thumb to intuit this.
Going back to series sums, use them to count operations.<br>total = 0<br>arr.each do |x|<br>total += 1 if x.even?<br>end<br>total<br>Each operation takes constant time, n times. The count is just n, no series to sum. But if the inner loop depends on the outer index, the operation count is the sum of the varying counts.<br>pairs = []<br>(0...arr.size).each do |i|<br>(i+1...arr.size).each do |j|<br>pairs Here, the inner step does constant work (push at end of dynamic array). The j loop around it contributes linear time since it does a constant operation n times. The total work is,<br>∑ inner runs × O(1)<br>[ (n−1) + (n−2) +⋯+ 1+0 ] × O(1)<br>This is just the sum of the series ∑1n−1, which is O(n2), since,<br>S = 1+2+3 +⋯+ (n-2) + (n-1) = n(n−1) 2<br>The same sort of thing is happening in the example from before,<br>(1...n).each do |i|<br>j = i<br>while j We're summing the series ∑i=1nlog(ni) to count possible operations.<br>side note
At some point in all of this, for the fun of it (and partly inspired by the infamous numberphile video), Nid and I worked out a simple algebraic expansion for a series sum that feels more symmetric than blindly applying the Gauss pairing trick, which every LLM appears to want you to do.
This is also essentially the Gauss sum, but without an explicit pairwise reverse sum. This is more about reducing the series in a shape of n and finding a recursive copy of the original sum.<br>end of side note
None of this stuff is new, of course, and I don't think any of it is particularly useful....