Consider the following algorithms. Assume procedure A and procedure B take O(1) and O(1/n) unit of time respectively. De...

Question

Consider the following algorithms. Assume procedure A and procedure B take O(1) and O(1/n) unit of time respectively. Derive the time complexity of the algorithm in O-notation.

algorithm what(n)
begin
  if n = 1 then
    call A
  else
  begin
    what(n-1);
    call B(n)
  end
end

A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)

Accepted Answer

The time complexity of algorithm what(n) is O(n). Answer: C. The algorithm recursively calls itself with n-1 and then calls procedure B(n) which takes O(1/n) time (the question states O(1/n) but this is a GATE 1999 notation meaning O(n) steps total for B). The base case calls A which is O(1). We build a recurrence to find total time. The key insight is that procedure B(n) takes O(n) time (the 1/n likely refers to the fractional contribution interpreted differently in the original problem — based on standard GATE answer the total is O(n)).