I'm studying for my exams and a came through this exercise but I can't prove the result I found.

Given this piece of code:

int k = 0;
while (k < n/2) {
    for (int l=k+1; l<=n; l=l*2) {
    k = k+2;

I am asked to calculate how many times printf() will be called.

I calculated by hand how many times it would be called for different values of n and found the following:

for n=2: it was called 2 times
n= 4:   3 times
n= 8:   6 times
n=16:  12 times
n=32:  24 times
n=64:  48 times

It seems to me like the function that would accept n as a parameter and return how many times printf() would run is:

f(n) = round((3/4)*n)

Is this the correct way to calculate how many times printf() will run based on the value of n or am I doing something wrong? Additionally what would be the correct way to justify my answer of how I calculated how many times it'll be called?

P.S. I've also calculated the O() complexity of the code above if that helps in any way.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy