# Time complexity of algorithm computing averages

I am new, and wanted to see if someone can help me.

What is the running time of your algorithm (below) with respect to the variable $n$? Give an upper bound of the form ${\cal O}(f(n))$ and a lower bound of the form $\Omega(g(n)).$ Can you characterize the asymptotic running time by by some $\Theta(h(n))$?

The algorithm:

Input: $A[1 \ldots n]$ array of floating point numbers

Output: Two dimensional array $M,$ such that $M[i][j]$ is the average of $A[i],\ldots, A[j],$ for all $i \le j,$ 0 for all $i>j.$

for i := 1 to n do
for j := 1 to n do
if i > j then M[i][j] := 0
else
sum := 0;
d := j-i+1;
l := i;
r := j;
do
sum := sum + a[l];
l++;
while (l <= r)
M[i][j] := sum / d;
print M[i][j];
end for
end for


Can someone give me an upper and lower bound?

I guess the algorithm complexity is ${\cal O}(n^3)$ on average, because of the quadratic complexity of the 2 for loops and the inner while loop which takes $O(n)$ time, which has the overhand over the assignments operations which takes $O(1)$ time.

But what is the upper and lower bound? And asymptotic running time by by some $\Theta(h(n))$?

-
I suggest you post this on area51.stackexchange.com and cstheory.stackexchange.com –  Kirthi Raman Mar 15 '12 at 17:31
@KirthiRaman cstheory.SE is for research-level questions in computer science. This is an undergrad-level question. I guess by area51.SE you mean this propsal for cs.SE. Unfortunately, cs.SE is private beta right now. They say it will go public in about 5-6 days from now I guess. –  user2468 Mar 15 '12 at 17:43
This question was already asked on cstheory.se; it was quickly closed for being off-topic. –  JeffE Mar 15 '12 at 22:04
Also asked and closed on MathOverflow. –  JeffE Mar 16 '12 at 7:00
I do not understand if this is a forum or i do not know what. The idea behind a forum is to develop a discussion as I think i tried to make. I just try to get rid with my problem and i tried to develop a solution by my own, the algorithm and the identification of the complexity. BUT i see that it is like i asked something terrible. I do not pretend u give me an answer on this task, because at the end i should undestand what is behind and be able to solve it by my own. I just ask to help me to understand the right approach, the idea which is behind and give me some hints, like Johannes made. –  pamatull Mar 16 '12 at 9:25

As you states, the algorithm runs in $O(n^3)$, which is actually the upper bound for the reasons you described.
To find a lower bound, note that it sufficient to find out the running time of the body of the inner for loop in terms of $i$, $j$ and $n$ (in fact, you will find that $n$ does not matter - why?). Denote this by $r(n,i,j)$. Then the running time of the whole algorithm is $\sum_{i=1}^n \sum_{j=1}^n r(n,i,j) + \Omega(n)$, where the final $\Omega(n)$ comes from the time required for executing the for loops.
If it is $n/2$ in the average case, that means that $r \in \Omega(n)$ (i.e., the inner part of the for loops runs in $\Omega(n)$). Hence, the overall algorithm is in ...? –  Johannes Kloos Mar 15 '12 at 18:01