Time Complexity Of The Below Program

Question

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

In the above program, I was asked to find the time complexity where procedure A takes O(1) time and procedure B takes O(1/n).

I formed the recurrence relation T(n) = T(n-1) + O(1/n)

And solving it, I got T(n) = O(log n) since we will get harmonic series if we solve it by using back substitution method and time complexity to compute the sum of harmonic series is O(lgn). But the answer is given as O(n). I am not able to figure out how they got that answer. In the explanation they have added a constant times n to the recurrence relation. I didn't get why we should add that constant times n. Please help me in understanding this.

Answer 1

This is likely a trick question set by the author / examiner to catch you out. You must note that the O(1) operations involved in each call to what (pushing arguments to stack etc.) overshadow the O(1/n) complexity of B – at least asymptotically speaking. So the actual time complexity is T(n) = T(n - 1) + O(1), which gives the correct answer.