What is the time complexity of the SearchInWindow algorithm?

Question

I wonder what the time complexity of the following algorithm is.

function SearchInWindow(p)
        for l ← 1 ... L do
                c_l ← CountOccurrences(p, l)
        end for
end function

The CountOccurrences returns the number of occurrences of a fragment of the length l positioned at the position p in the window (p + 1 ... p + W − 1), where W is the window length.

The CountOccurrences is in O(l × W). The p is the pointer to the data and should not affect the time complexity.

My guess is binom(L+1, 2) × W. But here I am not at all sure.

Answer 1

Let's take a look at the time complexity.

CountOccurrences takes a parameter l (and also p, but as it does not affect the time complexity, we will disregard it), and complete in O(l × W).

You're running a loop from 1 to L and calling CountOccurences with each value.

The time complexity of that is:

O(1 × W) + O(2 × W) + O(3 × W) + ... + O(L × W)
= O(W × (1 + 2 + 3 + ... + L))
= O(W × 1/2 × (L²+L)

Note that we can disregard the constant. Additionally, L² >> L, so O(L²+L) = O(L²).

So we have: = O(W × L²) as the final answer.

---

Note: Your answer of binom(L+1, 2) × W given in the question is technically equivalent as my answer, but since 2 in binom(L+1, 2) is a constant, we can simplify it further.