Сложность времени программы ниже

Question

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 (1 / n).

Я сформировал рекуррентное соотношение T (n) = T (n-1) + O (1 / n)

И, решив его, я получил T (n) = O (log n), поскольку мы получим ряд гармоник, если мы решим его с помощью метода обратной подстановки, а сложность по времени для вычисления суммы рядов гармоник составляет O (lgn).Но ответ дается как O (n).Я не могу понять, как они получили этот ответ.В объяснении они добавили постоянные времена n к рекуррентному соотношению.Я не понял, почему мы должны добавить это постоянное время п.Пожалуйста, помогите мне понять это.

Answer 1

Вероятно, это вопрос с подвохом, заданный автором / экзаменатором, чтобы поймать васВы должны заметить, что операции O(1), участвующие в каждом вызове what (перевод аргументов в стек и т. Д.), Затеняют сложность O(1/n) B - по крайней мере асимптотически .Таким образом, фактическая сложность времени равна T(n) = T(n - 1) + O(1), что дает правильный ответ.