Determining running time

Question

could you help me to determine the running time? O, Ω and Θ.

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;
er := j;
do
sum := sum + a[l];
l++;
while (l<=r)
M[i][j] := sum / d;

I have some problems with nested loops, 2 "for" and an inner "do" for instance. Could you maybe also suggest a method that could help me to do this? Thank you

Answer 1

I assume your do while loop is inside of for like ,

for i..n do
for j..n do
do 
while (x<n)
done
done

then time complexity will be n*n*n i.e. n^3 with worst case assumptions for "do while" loop.

if your do while loop is outside then it will be,

for i..n do
for j..n do
done
done
do 
while (x<n)

then (n*n + n) in worst case.

Answer 2

Each for loop is valued by the number of repeats. Nesting is multiplying the runtime. Example:

for x=0..n
  for y=0..m

would be n*m.

Side by side loops would be added, for example:

for x=0..n
  for y=0..m
for i=0..p
  for j=0..p

would be estimated as n*m+p^2