Question 1:

Let $f(n)=n^3$ and $g(n) = 7n^3 + 5n^2 + 8n + 3$. Which of the following best expresses the relation between $f(n)$ and $g(n)$?

1. $f(n)$ is $O(g(n))$
2. $g(n)$ is $O(f(n))$
3. Both A and B are true
4. None of the above

Question 2:

We know that the runtime of an algorithm is $O(n^2)$. Then, for a fairly large input size, doubling the size of the input will have the following effect on the runtime:

1. runtime will double
2. runtime will quadruple
3. runtime will be squared
4. runtime will be unchanged

Question 3:

Consider the following code snippet:

 for (int i=0; i<n; i++) {
   for (int j=0; j<n/2; j++) {
     offset1 = i*width + j;
     offset2 = i*width + width-1-j;
     for (int k=0; k<3; k++) {
       swap(A, offset1+k, offset2+k);
     }
   }
 }

The swap operation is executed:

1. $O(n)$ times
2. $O(n \log n)$ times
3. $O(n^2)$ times
4. $O(n^3)$ times

Question 4:

Consider the following code snippet:

  stringList *s = new arrayStringList();
  s->insertAtTail("hello");
  s->insertAtTail("fish");
  s->insertAtHead("pumpkin");

What is the content of the list?

1. hello, fish, pumpkin
2. pumpkin, hello, fish
3. pumpkin, fish, hello
4. fish, hello, pumpkin
5. none of the above