can use diagonal matrix in a formula to figure out how many characters would occur in all substrings of a string 's'?

Question

Math experts -

I'm working through a simple "big O" analysis of algorithms problem comparing two approaches to the longest substring problem. One approach is brute force: checking all possible substrings and selecting the longest.

I wanted to quantify the complexity of this approach in terms of character compares.
So I need a formula to figure out how many characters would occur in all substrings of a string "s".

Suppose the target string is 'mouse' and the string to check is "house" (in which case the answer is "ouse"), then all the substrings to check would be

house   ouse     use  se    e
hous    ous      us   s
hou     ou       u
ho      o
h

Which seems to inidicate that the formula would involve summing all the cells of a diagonal matrix, whose columns are given by the formula:

n       n-1     n-2     ...         1
n-1     n-2     n-3
n-2     n-3     n-4
n-3
.
.
.
1

I'm guessing this is solveable by some kind of series matrix sum thingee.. But my linear algebra is a bit of a work-in-progress. Any advice or tips much appreciated.

thanks / Chris

Answer 1

For the first column, we have the sum of numbers from $1$ to $n$, for the second column the sum from $1$ to $n-1$, and so on. The summation of all the cells of the matrix will be $$\begin{align}S&=\sum_{m=1}^n\sum_{k=1}^mk\\&=\frac{n(n+1)}{2}+\frac{(n-1)n}{2}+\cdots +1\\&=n^2+(n-2)^2+(n-4)^2+\cdots+1\end{align}$$ We have a sum of squares, of either odd or even numbers. Thus, two cases need to be considered: when $n$ is even, and when $n$ is odd.

For the even case we have $$\begin{align}S&=\sum_{m=0}^{(n/2)-1}(n-2m)^2\\&=\sum_{m=0}^{(n/2)-1}n^2-4n\sum_{m=0}^{(n/2)-1}m+4\sum_{m=0}^{(n/2)-1}m^2\\&=\frac{n^3}{2}-\frac{n^2(n-2)}{2}+4\left(\frac{\left(\frac{n}{2}-1\right)^3}{3}+\frac{\left(\frac{n}{2}-1\right)^2}{2}+\frac{\left(\frac{n}{2}-1\right)}{6}\right)\end{align}$$ As regards the odd case, the formula is $$\begin{align}S&=\sum_{m=0}^{(n-1)/2}(n-2m)^2\\&=\sum_{m=0}^{(n-1)/2}n^2-4n\sum_{m=0}^{(n-1)/2}m+4\sum_{m=0}^{(n-1)/2}m^2\\&=\frac{(n+1)n^2}{2}-\frac{n(n^2-1)}{2}+4\left(\frac{\left(n-1\right)^3}{24}+\frac{\left(n-1\right)^2}{8}+\frac{\left(n-1\right)}{12}\right)\end{align}$$