A general method for analyzing the running time of any algorithm is to walk through the algorithm step by step, counting the number of statements executed and express this count as a function of the "size" of the input.
For example, suppose we defined a predicate, isSorted, which would take as input an array $a$ and the size, $n$, of the array and would return true if and only if the array was sorted in increasing order. It might look like this
bool isSorted(int *a, int n) {
if (n == 1)
return true; // a 1-element array is always sorted
for (int i = 0; i < n-1; i++) {
if (a[i] > a[i+1]) // found two adjacent elements out of order
return false;
}
return true; // everything's in sorted order
}
Clearly, the size of the input here will simply be $n$, the size of the array. How many steps will be performed in the worst case, for input $n$?
- The first if statement counts as 1 step
- The for loop will execute $n-1$ times in the worst case (assuming the internal test doesn't kick us out), for a total time of $n-1$ for the loop test and the increment of the index.
- Inside the loop, there's another if statement which will be executed once per iteration for a total of $n-1$ time, at worst.
- The last return will be executed once.
So, in the worst case, we'll have done $1+(n-1)+(n-1)+1$ computations, for a total run time $T(n)\le 1+(n-1)+(n-1)+1=2n$ and so we have the timing function $T(n)=O(n)$.
For non-recursive algorithms, the process is, in theory, simple:
- Find a parameter, $n$, that expresses the "size" of the input. Walk through the algorithm, assuming
- Every statement executed will take time 1,
- Every if statement will take its longest branch,
- Every loop will iterate the maximum number of times allowable.
Then express the run time of your algorithm as a function of the sum of statements executed, using (2) through (4) above.
For recursive algorithms, you do the same thing, only this time you add the time taken by each recursive call, expressed as a function of the time it takes on its input.
For example, let's rewrite, isSorted as a recursive algorithm:
bool isSorted(int *a, int n) {
if (n == 1)
return true;
if (a[n-2] > a[n-1]) // are the last two elements out of order?
return false;
else
return isSorted(a, n-1); // is the initial part of the array sorted?
}
In this case we still walk through the algorithm, counting: 1 step for the first if plus 1 step for the second if, plus the time isSorted will take on an input of size $n-1$, which will be $T(n-1)$, giving a recurrence relation
$$
T(n) \le 1 + 1 + T(n-1) = T(n-1) +O(1)
$$
Which has solution $T(n)=O(n)$, just as with the non-recursive version, as it happens.
With this done, lets analyze your algorithm. We'll compute the run time as a function of right - left. That will be the size, $n$, so we'll try to find a recurrence relation that expresses the run time, $T(n)$, as a function of $n$.
If $n>0$, the function will take 1 step for the if test and then pass to the second loop. This loop will iterate $n$ times, doing two swaps and calling itself recursively with arguments that we'd express as $n-1, n-2, \dots 1, 0$. In other words, we'll have
$$
T(n) \le T(n-1) + T(n-2) + \cdots + T(1) + T(0) + kn
$$
where the last term takes account of the loop overhead and the two swaps. We have reached our goal: the timing function for the algorithm satisfies the recurrence
$$
T(n) = T(n-1) + \cdots + T(0) + O(n)
$$
and of course, when $n=0$, i.e., when left = right we just print the contents of the array, which we can do in a (possibly large) constant amount of time.
Any questions? Just ask.
As did has already pointed out, $T(n)\sim2\sqrt{n}$. Any easy way to arrive at this conclusion is to pretend $T(n)$ is defined for all real numbers and continuous, and approximate
$$
1=T(n)-T(n-\lceil\sqrt{n}\rceil)\approx\sqrt{n}T'(n)
$$
for large $n$, which makes $T'(n)\approx1/\sqrt{n}$ and in turn, by integration, $T(n)\approx2\sqrt{n}$.
Computing $T(n)$ using Maple, indeed reveals that
$$
T(n)=2\sqrt{n}-\frac{\ln(2\sqrt{n}+1)}{\ln2}+\epsilon_n
$$
where $\epsilon_n\in[-0.1,1]$.
A more formal proof of $T(n)\sim2\sqrt{n}$ is possible, but a bit more technical.
Let's write $n'=n-\lceil\sqrt{n}\rceil$. Then,
$$
\left(\sqrt{n}-\tfrac{1}{2}\right)^2-\tfrac{5}{4}\le n-\sqrt{n}-1\le
n'
\le n-\sqrt{n}=\left(\sqrt{n}-\tfrac{1}{2}\right)^2-\tfrac{1}{4}.
$$
First, assume $T(k)\le2\sqrt{k}$ for $k<n$: this holds for $k<1$, which starts the induction. Then,
using $n'<(\sqrt{n}-1/2)^2$,
$$
T(n)=T(n')+1\le2\sqrt{n'}+1\le 2\left(\sqrt{n}-\tfrac{1}{2}\right)+1=2\sqrt{n}.
$$
Next, assume $T(n)\ge2\sqrt{n}-\tau(n)$ for some function $\tau(n)$. Using
$$
2\sqrt{n'} \ge \sqrt{(2\sqrt{n}-1)^2-5} \ge 2\sqrt{n}-1-\frac{5}{2\sqrt{n}-1},
$$
this makes
$$
T(n)=T(n')+1\ge 2\sqrt{n'}+1-\tau(n')
\ge 2\sqrt{n}-\frac{5}{2\sqrt{n}-1}-\tau(n'),
$$
and so $T(n)\ge 2\sqrt{n}-\tau(n)$ holds if we define $\tau(0)=0$ and
$$
\tau(n)=\tau(n')+\frac{5}{2\sqrt{n}-1}.
$$
In turn, we now have
$$
\frac{\tau(n)-\tau(n')}{n-n'}
=\frac{5}{(2\sqrt{n}-1)\cdot\lceil\sqrt{n}\rceil}
\le\frac{5}{(2\sqrt{n}-1)\cdot\sqrt{n}}
<\frac{5+\delta}{2n}
$$
for any $\delta>0$ and sufficiently large $n$. From this follows that $\tau(n)$ at worst is $O(\ln n)$.
Best Answer
We can compute exact formulas for your recurrence and not just at powers of two. Suppose we first solve the recurrence $$S(n) = 7 S(\lfloor n/2\rfloor) + \frac{18}{16} n^2$$ with $S(0)=0.$ (This will produce $S(1) = \frac{18}{16}$ instead of one, which we'll correct later.)
Then let $$n= \sum_{k=0}^{\lfloor \log_2 n\rfloor} d_k 2^k$$ be the binary representation of $n$ and unroll the recursion to get the following exact formula for $S(n):$ $$S(n) = \frac{18}{16} \sum_{j=0}^{\lfloor \log_2 n\rfloor} 7^j \left(\sum_{k=j}^{\lfloor \log_2 n\rfloor} d_k 2^{k-j} \right)^2 = \frac{18}{16} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^j \left(\sum_{k=j}^{\lfloor \log_2 n\rfloor} d_k 2^k \right)^2.$$ To get an upper bound on this consider a string of one digits, which gives $$S(n)\le \frac{18}{16} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^j \left(\sum_{k=j}^{\lfloor \log_2 n\rfloor} 2^k \right)^2 = \frac{18}{16} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^j \left(2^{\lfloor \log_2 n\rfloor+1}- 2^j\right)^2 \\ = \frac{18}{16} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{\lfloor \log_2 n\rfloor-j} \left(2^{\lfloor \log_2 n\rfloor+1}- 2^{\lfloor \log_2 n\rfloor-j}\right)^2 \\ = \frac{18}{16} \left(\frac{7}{4}\right)^{\lfloor \log_2 n\rfloor}2^{2\lfloor \log_2 n\rfloor} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{-j} (2-2^{-j})^2 \\=\frac{18}{16} 7^{\lfloor \log_2 n\rfloor} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{-j} (2-2^{-j})^2.$$ Now the sum term converges to a constant and we have for the upper bound the asymptotics $$\frac{18}{16} \times 7^{\lfloor \log_2 n\rfloor} \times \frac{49}{10} = \frac{441}{80} \times 7^{\lfloor \log_2 n\rfloor}.$$
For a lower bound consider a one digit followed by a string of zeros, which gives $$S(n)\ge \frac{18}{16} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^j 2^{2\lfloor \log_2 n\rfloor} = \frac{18}{16} 2^{2\lfloor \log_2 n\rfloor} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{\lfloor \log_2 n\rfloor-j} \\ = \frac{18}{16} 2^{2\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{\lfloor \log_2 n\rfloor} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{-j} = \frac{18}{16} 7^{\lfloor \log_2 n\rfloor} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{-j}.$$ The sum term once more converges to a constant and we get for the lower bound complexity the asymptotics $$\frac{18}{16}\times 7^{\lfloor \log_2 n\rfloor} \times\frac{7}{3} = \frac{21}{8} \times 7^{\lfloor \log_2 n\rfloor}.$$
Putting the two bounds together we get a complexity of $$S(n) \in \Theta(7^{\lfloor \log_2 n\rfloor}) = \Theta(2^{\log_2 7\times \lfloor \log_2 n\rfloor}) = \Theta(n^{\log_2 7}).$$
This being Strassen the point was to show that the complexity is better than $\Theta(n^3),$ the naive matrix multiplication, which it is, because $\log_2 7 < 3$.
To conclude this calculation we return to $T(n)$ which was supposed to have $T(1)=1$ and not $18/16.$ We can compensate for this by putting $$T(n) = -\frac{2}{16} 7^{\lfloor \log_2 n\rfloor} + S(n).$$ This term only changes the coefficient on the two bounds and does not affect the order of growth.
There are more Master Theorem type calculations at this MSE link.
Addendum. Interestingly if we compute the partial sums for the lower bound we obtain $$-\frac{2}{16} 7^{\lfloor \log_2 n\rfloor} +\frac{18}{16} 7^{\lfloor \log_2 n\rfloor} \sum_{j=0}^{\lfloor \log_2 n\rfloor} \left(\frac{7}{4}\right)^{-j} = -\frac{2}{16} 7^{\lfloor \log_2 n\rfloor} + \frac{18}{16} 7^{\lfloor \log_2 n\rfloor} \frac{1-4/7\times(4/7)^{\lfloor \log_2 n\rfloor}}{1-4/7} \\= -\frac{2}{16} 7^{\lfloor \log_2 n\rfloor} + \frac{18}{16} 7^{\lfloor \log_2 n\rfloor} \times \frac{7}{3} - \frac{18}{16} \times \frac{4}{3} \times 4^{\lfloor \log_2 n\rfloor} \\ = +\frac{5}{2} 7^{\lfloor \log_2 n\rfloor} - \frac{3}{2} \times 4^{\lfloor \log_2 n\rfloor},$$ which matches up perfectly with the formula that was proposed as an answer in the original question.