Find the time complexity of code that runs three loops

Question

I have this piece of code, and I would like to find its temporary complexity. I am getting ready for an interview, and I think it is a little complicated.

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 do not know why, but I cannot relate this expression and find complexity.

Any help on resolving this issue?

Answer 1

Allows you to write it as:

(n/2)*log(1) + (n/4)*log(3) + ... + 1*(log(n-1)). Which is equal to:

< n * [log(2^i)/(2^i) for i in range 1...n] .
= n * [log(2)/2 + log(4)/4 + log(8)/8 + ... + log(n)/n)] 

It means that O(n)

Answer 2

Since you have not shown any progress, I will give you top-level hints:

• let log_t = log2 (t). What is log_t as a function of i?
• Note that the outer loop runs log2 (n) times.
• How long is the cycle running j?
• n, 32. i sum +=? n?