0
$\begingroup$

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))$?

  • 0
    I suggest you post this on http://area51.stackexchange.com and http://cstheory.stackexchange.com2012-03-15
  • 2
    @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](http://area51.stackexchange.com/proposals/35636/computer-science). Unfortunately, [cs.SE is private beta right now](http://cs.stackexchange.com/). They say it will go public in about 5-6 days from now I guess.2012-03-15
  • 0
    This question was already asked on cstheory.se; it was quickly closed for being off-topic.2012-03-15
  • 0
    Also asked and closed on MathOverflow.2012-03-16
  • 0
    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.2012-03-16

1 Answers 1