# 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.

The asymptotic running time will, of course, lie between the upper and the lower bound. In this example, it will be obvious as soon as you know the lower bound.

-
Thank u for the answer... hmm so if u say that the lower bound is related to the work inside the second for loop, i can observe that in half of the cases there's just an assignment which has constant complexity O(1). In the other half there's another loop which iteration depends on i and j value (so this is why u say that n does no matter. Right?). In the average case it will be executed n/2 time, because of the condition i gave i<=j and it is linear dependent of n. Am i right? .... what's then the lower bound of this algorithm? .. –  pamatull Mar 15 '12 at 17:59
Yes, Johannes the method and the right approach. This is my last exam at the university and i have not the possibility to frequent my lessons, so i need to learn it by my own. Anyway if the inner work of the inner loop takes Ω(n) time and the 2 for loops takes O(n^2) time, guess the overall running time is Ω(n^3) which is also the lower bound. Do not know if i am on the right way :) –  pamatull Mar 15 '12 at 17:59
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
PS: This looks very much like homework, so I would rather not give the answer directly, but help you in learning the methods instead. –  Johannes Kloos Mar 15 '12 at 18:01
PPS: You can just edit your post instead of writing an answer. –  Johannes Kloos Mar 15 '12 at 18:03