The running time of the following algorithm is best described by which option?…
2002
The running time of the following algorithm is best described by which option? Procedure A(n): if n <= 2, return 1; otherwise return A(√n).
- A.
O(n)
- B.
O(log n)
- C.
O(log log n)
- D.
O(1)
Attempted by 8 students.
Show answer & explanation
Correct answer: C
The recurrence for the running time is T(n) = T(√n) + O(1). Substitute n = 2^m and define S(m) = T(2^m). Then S(m) = S(m/2) + O(1), which solves to O(log m). Since m = log n, the running time is O(log log n). Therefore, the correct option is O(log log n).