Question

JAVA

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

1. Assigning each student in class a number 1 to n will take O(n) time. Since there will be n/2 odd numbered students I.e. O(n) whether s/he is left/right handed will take O(n) time. Hence total time complexity is O(n) + O(n) + O(n) = O(n).

Hence option b is correct .

2. Since after each successive quiz, half of the students drop the course. Hence if there are k quizzes happen, then number of students remain will be n/2^k. Since at last only 1 student remains,

=> n/2^k = 1

=> 2^k = n

=> k = log₂ n = O(log n)

Hence option c is correct.

3. Here all statements except statement d are false.

Option a, b, c are false since traversing an element of array is less expensive then linked list . Option e is false since accessing first element at linked list will fake O(1) time.

Option. d is correct since dropping 1 element will take O(1) time and hence dropping n elements one by one will take n*O(1) = O(n).

Please comment for any clarification .