大 O 符号：帮助我证明我的教授是错误的

Question

我是一名 UI 开发人员，但我的学位是英语，所以我一直在尝试学习一些更具形成性的 CS classes 来提高我的基础.现在我在数据结构 class 中，我们的 class 最近出现了以下问题：

a) Assume evaluating a function f(n) in the pseudocode below takes Θ(n) time.

i = 1; 
sum =0;
    while (i <= n) 
        do if (f(i) > k) 
            then sum += f(i);
        i = 2*i;

What is the running time (use an asymptotic notation) of the above code? Justify your answer.

我的回答以及 class 中的许多其他回答是 n log n，因为外部 while 循环将运行 in log(n)和while循环内部的渐近运行时间(Θ(n)) 与 n 紧密绑定。

教授的回答是运行 n 次。不知道 k 或者 f(n) 实际上是，这怎么可能？

Answer 1

n = 4 的时间：1 + 2 + 4 = 7 步

n = 8 的时间：1 + 2 + 4 + 8 = 15

n = 16 的时间：1 + 2 + 4 + 8 + 16 = 31

2的幂的总时间是2n-1，总计O(n)...对不起O:)

Big O Notation: Help me prove my professor wrong