Search code examples
performanceruntimenested-loopspseudocode

Determining running time

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

Solution

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