0

What is the Big-O complexity of iterating over every possible non-empty substring of a string of length $N$?

The simple way to do the iteration over string $S$ is:

for i in 1 .. N:
    for j in (i+1) .. N:
        S[i .. j]

Clearly this is more complex than $\mathcal{O}\left(N\right)$ but less complex than $\mathcal{O}\left(N^2\right)$, but I'm not sure how to understand the complexity of these nested loops.

brianmearns
  • 837
  • You have $\frac{N(N+1)}{2}$ iterations – Tryss Feb 24 '15 at 15:18
  • @Tryss: Thanks, would you be able to explain this a little? In fact, I actually need to add a third nested loop, which iterates j/2 times, so I'm not sure how to extrapolate from your answer to a more general solution. – brianmearns Feb 24 '15 at 15:21
  • 1
    Your inside loop do N-i iterations, so the total number of iterations is given by $$\sum_{i=0}^N N-i = \sum_{i=0}^N i = \frac{N(N+1)}{2}$$ This is a classical formula, and there exist similar formula (but more complex) for $\sum_{i=0}^{N} i^n$. Actually $\sum_{i=0}^{N} i^n$ is a n-th degree polynomial – Tryss Feb 24 '15 at 15:25

1 Answers1

2

$$ S = (1+ 1+ \ldots 1) + //\text {n times}\\ (1+1+ \ldots 1) + //\text{n-1 times} \\ \ldots 1 $$ Hence $S = 1 + 2 + \ldots (n-1) +n = \frac{n(n+1)}{2}$

Alex
  • 19,262