Value of variables and Time Complexity of this Algorithm

Question

Questions:

1. p and q value at end of this algorithm execution
2. Time Complexity of this algorithm

My Answer:

Answer 1

The first inner loop increments p a number of times equal to the base-2 logarithm of n. As the outer loop executes n times, the final value of p is n.lg(n).

Now the second loop increments q a number of times equal to lg(p), where p takes the values k.lg(n), or 1, 2, 3, ... n times lg(n). The final value of q is lg(n!)+n.lg(lg(n)).

The time complexity follows easily, as the number of operations is proportional to the number of incrementations of p plus those of q plus some negligible overhead. Finally, Θ(lg(n!)) = Θ(n.lg(n)).

---

Note that these are only approximations, as the true number of iterations is the floor of the logarithm, not the logarithm.