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) {
printf("\n");
}
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.