Q1

• Start with the outer loop
  • How many iterations of the outer loop ? N
  • How much time needed per iteration ? Note that the inner loop executes only 3 times (k varies from 1 to 3).
• Inner loop uses O(3*1) time. But in our arithmetic, we drop all the constant factors. So, we say that inner loop is O(1)
• Total time is N * O(1) = O(N)

Q2

• First of all notice that we have a sequence of two statements. First one is a nested for loop and the second one is a simple for loop. So, the overall running time will be determined by adding up the running time of these two statements.
• Lets analyze the nested for loop first

      for (int r = 0; r < N; r++) {
      	for (int c = 0; c <=r; c++) {
  	    m[r][c] = 1;
  	}
      }
  

  • Note that the outer loop executes N times.
  • If you notice the inner loop, then the number of times the inner loop is executed depends upon the value of the index of the outer loop, ie, when r = 0, the inner loop executes 1 times, when r = 1, the inner loop executes 2 times, and so on.
  • So, the total number of times, the statement in the inner loop gets executed is given by 1 + 2 + .... + N, which is equal to N(N+1)/2. And using "our" arithmetic, we get the running time of above piece of code as O(N^2)
• Let us now analyze the second statement, ie, the other for loop

      for (int d = 0; d < N; d++) {
          m[d][d] = 0;
      }
  

  • This is a simple for loop, running time of which is O(N)
• Thus the running time of the two loops together is given by the sum of the running times of the individual loops, ie O(N^2) + O(N) . Drop the lower order terms and we get O(N^2)
• NOTE that quite a few of you had O(N^3) as answer to this question which you can see is not correct. When you have a sequence of statements, their running times add up. In this question we have a sequence of two statements, both of which are for loops (the first one is a nested for loop and the second one is a simple for loop). So, when you want to calculate the running time of these two statements taken together, you will not multiply their individual running times, you will add them. Note that the answer would have been O(N^3) if the code looked something like this

      double m[N][N];
  
      for (int r = 0; r < N; r++) {
      	for (int c = 0; c <=r; c++) {
  	    m[r][c] = 1;
  	    
  	    for (int d = 0; d < N; d++) {
          	m[d][d] = 0;
      	    }
  	}
      }