Algorithm Run Time Matrix

Question

I am having trouble figuring out the tight bound and the lower bound for this pseudocode. Could anyone help ?

Array S;

for i <-- 0 to n-1
  for j <-- 0 to n-1 
    for k <-- 0 to n-1 
       M[i][j] = M1[i][k]*M2[k][j]
return M

Thanks!

You might be better off at cs.stackexchange.com with this question. — thomasfedb
– thomasfedb, Commented Mar 5, 2015 at 3:07

Log_n · Accepted Answer · 2015-03-05 03:08:40Z

4

Three nested loops and no options to end early would mean a complexity of n^3, best and worst case are the same.

answered Mar 5, 2015 at 3:08

Log_n

4042 silver badges5 bronze badges

Sign up to request clarification or add additional context in comments.

1 Answer 1