Time Complexity of algorithm with nested if statement and for loops

Question

So im trying to solve this question but me and my friends are a bit confused by it

for (Int64 i = 1; i < Math.Pow(2, n); i = 2*i)
{
    if (i <= 4 || i >= Math.Pow(2, n - 2))
    {
        for (Int64 j = n; j >= 0; j = j - 2)
        {
            //constant number of C operations
        }
    }
    else
    {     
        for (Int64 j = n; j > 1; j = (Int64) Math.Ceiling((double) j/2))
        {
            //constant number of C operations
        }
    }
}

I get that the outer loop is O(n) but I can't get what the inner part is, I'm pretty sure it's just O(n) since the largest of the inner for loops i the top one at O(n) as apposed to the lower one which is O(log n).
Is this the right way in thinking about it? or am i wrong

Answer 1

but I can't get what the inner part is, I'm pretty sure it's just O(n) since the largest of the inner for loops i the top one at O(n) as apposed to the lower one which is O(log n)

The top inner loop is indeed Θ(n). It does not follow that the inner part is Θ(n), at least not in the sense that you should multiply this by the Θ(n) of the outer loop, obtaining an overall Θ(n²). This is because the top loop in the inner part is executed only a constant number of times. The Θ(n) of the top inner loop should be added to that of the outer loop.

The overall complexity of this code is Θ(n log(n)). Specifically, it is Θ(n) Θ(log(n)) (total complexity of executing the bottom inner loop altogether) + Θ(n) + Θ(n) (total complexity of executing the top inner loop altogether).