## Algorithm Analysis quiz

Consider the code fragment:
```  for (int k = 1; k < N; k = k*2)
sum++;
```
How many addition operations does the above code fragment perform as a function of N?

~N
~N/2
~lg N
~0.5 lg N

Which of the following order-of-growth classifications represents the worst case number of array accesses used to binary search an array of size N?
constant
logarithmic
linear
linearithmic

Which of the following order-of-growth classifications represents the best case number of array accesses used to binary search an array of size N?
constant
logarithmic
linear
linearithmic

Which of the following functions is O(N3)?

11 N + 15 lg N + 100
0.5 * N2
25,000N3
All of the above

Which of the following functions is big-omega(N lg N)?

(i) 11 N + 15 lg N2 + 100
(ii) 0.5 * N2
(iii) 25,000N3
only (i) and (ii)
only (ii) and (iii)
All of the above

The code below shows the instance variables for WeightedQuickUnionUF.
```public class WeightedQuickUnionUF {
private int[] id;    // id[i] = parent of i
private int[] sz;    // sz[i] = number of objects in subtree rooted at i
private int count;   // number of components
...
```
How much memory does a WeightedQuickUnionUF object use as a function of N? Give your answer in bytes in tilde notation.
~2N
~3N
~8N
~12N