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(N³)?

11 N + 15 lg N + 100
0.5 * N²
25,000N³
All of the above

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

(i) 11 N + 15 lg N^{2 + 100

(ii) 0.5 * N²

(iii) 25,000N³

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}