int fun1 (int n) {
int i, j, k, p, q = 0;
for (i = 1; i < n; ++i) {
p = 0;
for (j = n; j > 1; j = j/2)
++p; //this "for loop" is ending here
for (k = 1; k < p; k = k * 2)
++q;
}
return q;
}
p is incrementing $logn$ times hence $p=logn$
and after the loop ends, inner "for loop" is also computing $logp$ i.e. $log(logn)$ times.
so final value of $q=n*O(log(logn))$
But what if program is like this:-
int fun1 (int n) {
int i, j, k, p, q = 0;
for (i = 1; i < n; ++i) {
p = 0;
for (j = n; j > 1; j = j/2) {
p++; //here loop is not ending here
for (k = 1; k < p; k = k * 2)
++q;
}
}
return q;
}
then for one single value of $i$ value of $q$ will be like this
$q=1*1+2*2+4*3+8*4+16*5+32*6+....n*logn$
$q=\sum_{i=1}^{logn}$$2^{i}*i$
$q=n+O(nlogn)$
after every loop we are resetting the value of $p=0$
So, final value of $q=n^{2}*O(logn)$