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:

left = 0
(0...n).each do |right|
  while bad
    left += 1
  end
end

Here, right and left only move forward once, so the total amount of movement is 2n, linear time.

Similarly, a nested loop that doubles against the cut off internally:

(1...n).each do |i|
  j = i
  while j < n
    j *= 2
  end
end

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:

`i`	→ `2i`	→ `4i`	→ `8i`	→ `n`

Repeated doubling (or halving) that reaches n is logarithmic, so you get an inequality like this:

$2^{k} \times i < n$

$2^{k} < \frac{n}{i}$

$k < \log (\frac{n}{i})$

So for every i, $\log (\frac{n}{i})$ is the number of operations. For all i, it's $\sum \log (\frac{n}{i})$ , since we're just counting the operations (k), not the actual value (that's what the program is for!)

$\sum_{i = 1}^{n} \log (\frac{n}{i}) = n \cdot \log (n) - \log (n!) \approx n$

$\sum \log (\frac{n}{i})$ 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.

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 (\log \log n)$ , I was having a hard time understanding why:

i = n
while i > 2
  i = Math.sqrt(i)
end

After some dubious scratch math, I managed to arrive at a no-prior-inspiration analysis. The only prior is the definition of logarithm itself $2^{x} = n$ , x = $\log_{2} (n)$ . Or more generally, $B^{x} = n$ , x = $\log_{B} (n)$ , where B is the base.

In the code above, we start with n and repeatedly take square roots. Square roots are simply fractional powers, $n^{\frac{1}{2}}$ .

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:

iteration	value	is also
${(2^{16})}^{\frac{1}{2}}$	256	→ $2^{8}$
${(2^{8})}^{\frac{1}{2}}$	16	→ $2^{4}$
${(2^{4})}^{\frac{1}{2}}$	4	→ $2^{2}$
${(2^{2})}^{\frac{1}{2}}$	2	→ $2^{1}$
${(2^{1})}^{\frac{1}{2}}$	1	→ <stop>

In other words, we're doing,

iteration	value	is also
${(2^{16})}^{\frac{1}{2}}$	256	→ $2^{8}$
${(2^{16})}^{\frac{1}{4}}$	16	→ $2^{4}$
${(2^{16})}^{\frac{1}{8}}$	4	→ $2^{2}$
${(2^{16})}^{\frac{1}{16}}$	2	→ $2^{1}$
${(2^{16})}^{\frac{1}{32}}$	1	→ <stop>

This is just, ${(n)}^{\frac{1}{2^{k}}}$ where, n= $2^{16}$ (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 2¹⁶ 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.

So it'd be fair to say that our loop represents this inequality:

$n^{\frac{1}{2^{k}}} > cut_off$

or, in powers of two (so we're working against same-base logs),

${(2^{m})}^{\frac{1}{2^{k}}} > cut_off$

We need to solve for k, but it's stuck as a non-trivial exponent on top, but since $2^{x} = n$ , x = $\log_{2} (n)$ , we can use that to pull it down:

$\frac{m}{2^{k}} > \log_{2} (cut_off)$

$m > 2^{k} \cdot \log_{2} (cut_off)$

$\frac{m}{\log_{2} (cut_off)} > 2^{k}$

$2^{k} < \frac{m}{\log_{2} (cut_off)}$

$k < \log_{2} (\frac{m}{\log_{2} (cut_off)})$

since, $2^{m} = n$ , m = $\log_{2} (n)$

$k < \log_{2} (\frac{\log_{2} (n)}{\log_{2} (cut_off)})$

Since $\log_{2} (cut_off)$ is constant, we get $O (\log \log n)$ ... 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.

total = 0
arr.each do |x|
  total += 1 if x.even?
end
total

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.

pairs = []
(0...arr.size).each do |i|
  (i+1...arr.size).each do |j|
    pairs << [arr[i], arr[j]]
  end
end
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,

$\sum inner runs \times O (1)$

$[(n - 1) + (n - 2) + \dots + 1 + 0] \times O (1)$

This is just the sum of the series $\sum_{1}^{n - 1}$ , which is $O (n^{2})$ , since,

$S = 1 + 2 + 3 + \dots + (n - 2) + (n - 1) = \frac{n (n - 1)}{2}$

The same sort of thing is happening in the example from before,

(1...n).each do |i|
  j = i
  while j < n
    j *= 2
  end
end

We're summing the series $\sum_{i = 1}^{n} \log (\frac{n}{i})$ to count possible operations.

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.

whiteboard math

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.

end of side note

None of this stuff is new, of course, and I don't think any of it is particularly useful. Program runtime optimization is a different art-form of measuring and profiling; it's rare that you're actually formally evaluating scaling laws for piecemeal algorithms. I started this whole thing off one weekend just lazily handing code snippets to LLMs to theoretically analyse out of curiosity, and enjoyed the back-and-forth so much that it became the whole point: a pedagogy mode to find links that I never examined before.

This is my preferred way of using LLMs these days. I've been working on a code-review plugin for emacs & magit with agents, pedagogical style. I hand-write all the code and use agents to validate, correct and guide me in the right direction.