Algorithm complexity

[pamatull]

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

Task:
What is the running time of your algorithm (the one u see BELOW) with respect to the variable n? Give an upper bound of the form O(f(n)) and a lower bound of the form Ω(g(n)).
Can you characterize the asymptotic running time by by some θ(h(n))?

avgMatrix
INPUT: A[1…n] array of floating point numbers
OUTPUT: Two dimensional array M, such that M[i][j] is the average of A[i] ...A[j] , for all i <= j, 0 for all i>j

PSEUDOCODE:
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];


Can give me someone an upper and lower bound?

I guess the algorithm complexity is O(n^3) on average, because of the quadratic complexity of the 2 for loops and the inner while loop which thakes 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 θ(h(n))?

[LB]

With big-O notation, you don't do 'on average', you do 'worst case scenario'.

[Albatross]

Yes, but can have a worst-case scenario for the best-case scenario, and a worst-case scenario for the average-case scenario. I think pamatull wanted the upper limit for the worst-case scenario and an upper limit for the best-case scenario.

-Albatross