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

1

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.

  • 0
    I just want to ask what is wrong on my question. I$f$ forum exists for developing discussions, or trying to get hints on some problems so my question is right, because i do not pretend that u give me an answer, just give me hints and an idea to approach the task. As u see in my topic i have not given a problem and waiting for answer, i have tried to do it by my own, i developed this algorithm to compute the average of an array of elements which populates at the end a two dimensional matrix and now i try to identify an upper and lower bound.2012-03-16