I'm a UI Developer by trade, but my degree is in English, so I've been trying try to take some of the more formative CS classes to improve my foundation. Right now I'm in a Data Structures class, and our class was recently presented with the following problem:
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.
My answer, along with many others in the class, was n log n as the outer while loop will run in log(n) and the asymptotic run time of the inside of the while loop (Θ(n)) is tightly bound to n.
The Professor's answer was that it would run in n time. Without knowing k or what f(n) actually is, how is this possible?
Time for n = 4: 1 + 2 + 4 = 7 steps
Time for n = 8: 1 + 2 + 4 + 8 = 15
Time for n = 16: 1 + 2 + 4 + 8 + 16 = 31
The total time is 2n-1 for powers of two, which amounts to O(n) overall... Sorry O:)