Question

1. What is the complexity of this algorithm?

Assign each student in the class a number from 1 to n, where n is the number of students. Then ask each of the odd-numbered students whether he or she is left-handed.

a. O(1)
b. O(n)
c. O(n ^ 2)
d. O(log n)

2. What is the complexity of this algorithm?

In a very difficult CS class, half the n students who originally signed up drop the course after the first quiz. After each successive quiz, half the remaining students drop. This continues until there is only one student remaining in the course.

a. O(n)
b. O(n ^ 2)
c. O(log n)
d. O(n log n)

3. Which statement is true?

a. traversing a linked list and traversing an array list have the same complexity
b. getting an item from an arbitrary index in an array list is generally more expensive than c. getting an item from an arbitrary index in a linked list
d. clearing (dropping all elements) from an array list is O(n)
e. deleting the first item from a linked list is O(n)

Answer 1