I have this piece of code and I would like to find its time complexity. I am preparing for interviews and I think this one is a bit tough.
int foo (int n)
{
int sum = 0;
int k, i, j;
int t = 2;
for (i=n/2; i>0; i/=2)
{
for(j=0; j<i; j++)
{
for(k=0; k<log2(t-1); k++)
{
sum += bar(sum);
// bar time-complexity for all inputs is O(1)
}
}
t = pow(2, i);
}
}
I don't know why but I am unable to bound this expression and find a complexity.
Any help on how to resolve this ?