22C:21: Computer Science II: Data Structures

Quiz 2: September 17, 2004


Consider the following piece of code.
		Matrix x;
		x = new Matrix(n, n);
		
		for(int i = 0; i < n; i++)
			x.addRow(0);
  1. What is the height and the width of matrix x (as a function of n) after the above piece of code has been executed?

    Answer: height is 2n and width is n.

  2. In Big-Oh notation, as a function of n, what is the running time of the above piece of code? Explain in 2 sentences.

    Answer: O(n^2). Recall that the Matrix class is implemented as a Vector with each element containing a Vector. Each call to x.addRow(0) moves all elements currently in the Vector down by one slot. So the total running time of the code fragment is

    O(n) + O(n+1) + O(n+2) + ... + O(n + (n-1)) = O(n^2)
    

Extra Credit True or False?

	1 + 2 + 3 + .... + sqrt(n) = O(n)
No need for any explanation. If you get this right you get 5 extra points. If you get this wrong 5 points will be subtracted from your total!

Answer: True.