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);

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

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