1
$\begingroup$

This question already has an answer here:

I'm trying to work through various exercises in Skiena's "Algorithm Design Manual." One problem that I am stuck on is as follows:

What value is returned by the following function? Express your answer as a function of n. Give the worst-case running time using Big Oh notation.

function conundrum(n)
    r:=0
    for i:=1 to n do
        for j:=i+1 to n do
            for k:=i+j-1 to n do
                r:=r+1
    return(r)

My first attempt at this problem began with trying to solve it when $n$ is even and my first observation was that $r$ is never incremented for any value of $i$ greater than $n/2$ (I am assuming that a statement along the lines of "$k:=l$ to $n$" is not executed for any $l>n$. Indeed, upon working out the above function for several different values of $n$, I thought that I could intuit that the sum calculated by the function had the following form $\sum_{p=1}^{n/2}\sum_{q=1}^{2p-1}q$-- to intuit this, I began the first loop at $i=n/2$ and worked backwards. Working this sum out, I got $\frac 1 {24} n(n(2n-3)-26)$. To my dismay, upon checking this answer, I found that the correct answer for even $n$ is $\frac 1 {24} n(n+2)(2n-1)$. Any thoughts or hints about what I am doing wrong?

$\endgroup$

marked as duplicate by Raphael Mar 29 '14 at 12:00

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.