Check on Summations

Question

I'm completing some time complexity analysis on loops which requires me to represent psuedocode loops as summations. I have two summations that I believe I have done to a degree of correctness, but am unsure. Here's the initial pseudocode for the first:

for i=1 to n:
    for j=1 to n:
        if i+j<n:
            for k=1 to n:
                sum++

I take this to mean the following:

$\sum_{i=1}^n\sum_{j<n-i}^n\sum_{k=1}^n 1$

$\sum_{i=1}^n\sum_{j<n-i}^nn = \sum_{i=1}^n n\sum_{j<n-i}^n$

$\sum_{i=1}^n n(n-(n-i)+1) = n\sum_{i=1}^n 1-i = n(\sum_{i=1}^n 1 - \sum_{i=1}^n i)$

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

So the overall time complexity of this loop (in the worst case) is $O(n^3)$. Is this accurate? I'm concern that the upper bound for my second summation is incorrect.

The second psuedocode is this:

for i=1 to n:
    for k=1 to n:
        sum++
        k=k/2

This psuedocode contains no tricky 'if' statement, but the $k=\frac{k}{2}$ confuses me a bit. Here's the summation I have:

$\sum_{i=1}^n\sum_{k=1}^n 1+\frac{k}{2} = \sum_{i=1}^n 1 + \frac{1}{2}\sum_{k=1}^n k$

$\sum_{i=1}^n n+\frac{n(n+1)}{4} = \sum_{i=1}^n n+ \sum_{i=1}^n\frac{n(n+1)}{4} = n\sum_{i=1}^n 1 + \frac{n^2}{4}\sum_{i=1}^n 1 + \frac{n}{4}\sum_{i=1}^n 1$

$n^2+\frac{n^3}{4} + \frac{n^2}{4}$

So the time complexity is $O(n^3)$. Again, I'm not sure if I handled that $k=\frac{k}{2}$ properly, so feedback would be appreciated!

Answer 1

In the first case the correct formula (for $n \geq 3$) is:

$$\begin{align} \sum_{i=1}^{n-2}\sum_{j=1}^{n-i-1} n &= \sum_{i=1}^{n-2} n(n-i-1) \\ &= n^2(n-2) - n\frac{(n-2)(n-1)}{2} - n(n-2) \\ &= \frac{(2n^3 - 4n^2) - (n^3 - 3n^2 + 2n) - (2n^2 - 4n)}{2} \\ &= \frac{n^3 - 3n^2 + 2n}{2} \\ &= \frac{n(n-1)(n-2)}{2} \end{align}$$ The $n-2$ in the upper limit of the sum is because values of $i \geq n-1$ never end up being computed in the second sum.

In the second case, I don't think the internal loop will ever finish. If we simulate what's happening on the third for loop we get:

k=1      % begin of the for loop
k <= n   % we enter the for loop
sum++    % computed, presumably now sum=1 (there were no sum=0 before)
k = k/2  % now k=0.5
k++      % in the end of the for loop, so k=1.5
k <= n   % we continue inside the for loop (assuming n >=2)
sum++    % computed, presumably now sum=2
k = k/2  % now k=0.75
k++      % in the end of the for loop, so k=1.75
k <= n   % we continue inside the for loop (assuming n >=2)
         % and so on for a long time
sum++    % computed, now sum is very large
k = k/2  % now k=0.999999...
k++      % in the end of the for loop, so k=1.99999...
k <= n   % we continue inside the for loop (assuming n >=2)
         % and the loop will continue forever

Therefore, you'll get $k=1$, $k=0.5$, $k=1.5$, $k=0.75$, ... approaching an infinite loop that with $k$ alternating between just under $k=1$ and just under $k=2$.

Are you sure it's not something else inside the internal loop? Perhaps sum += k/2?