Time complexity [closed]

Question

This question is for revision purposes from a past exam paper I just want to know if I am on the right track

1. int i=1;
2. while (i <= n) {
3.   for (int j=1; j<10; j++)
4.     sum++;
5.   i++;
6. }
7. for( int j = 1; j <= n; j++ )
8.   for( int k = 1; k <= n; k=k*2 )
9.      sum++;

1.) How many times is statement 4 executed?
A. O(n)
B. O(n^2)
C. O(log n)
D. O(n log n)
E. none of the above

Here I chose A

2.) How many times is statement 9 executed?
A. O(n)
B. O(n^2)
C. O(log n)
D. O(n log n)
E. none of the above

Because of line 8 (k=k*2) I chose C

3.) What is the running time of the entire code fragment?
A. O(n)
B. O(n^2)
C. O(log n)
D. O(n log n)

Since O(n)+O(logn)=O(n) so I chose A

Answer 1

Your answer 1 is correct, it's inside a loop controlled only by n.

Answer 2 is incorrect. It would be O(log n) if line 7 did not exist but, because line 7 is forcing lines 8 and 9 to run multiple times dependent on n, the answer is O(n log n).

Answer 3 is the correct reasoning but suffers from the fact answer 2 was wrong. O(n) + O(n log n) simplifies down to O(n log n).

So the answers are A, D and D.

Answer 2

I dont know how the questions where formulated, but if the wording is like you say, your examiner didnt know the right definition of big O (at least when he expects the "right" answers) – as "Big O functions include smaller". So something that executes as a function of n in f(n) = 10 n which is linear is also in O(n), O(n^2), O(n log n). If one asks for the "smallest" possible, your answers would be

1. Statement 4 is executed 10 n times, so A
2. Statement 9 is executed n*log n times, so D
3. Here it is executed the sum of both, n + n*log n so (here you lost an *n), so D would be the right.

So if multiple answers were possible and it was just asked for how much it is executed, the right answers would be

1. A,B,D
2. B,D
3. B,D