1

So I'm studying for my data structures midterm that's this monday, and my professor gave out a sample midterm with the answers, but I'm having a hard time understanding one of the questions.

Here's a screen cap:

enter image description here

Could someone give me a walk through of the math that's happening in each step? And possibly a conceptual explanation in computer science terms?

Connor Black
  • 147

1 Answers1

1

You see no matter what values i,j take, k goes from 1 to n. Thus cont will run n times runs of the first two loops. Consider i,j, fix i, j goes from 1 to i. Thus the total time complexity $$T(n)=n\cdot\left((1)+(1+2)+...+(1+2+...+n)\right)$$

Shuchang
  • 9,800