Theta time complexity of a recursive function

Finding the Theta order runtime of the following snippet of code is giving me trouble:

void foo(int n)
{
    if (n <= 1)
    {
        return;
    }

    for(i = 0; i < n; i++)
    {
        cout << endl;
    }

    foo(n / 2);
    foo(n / 2);
}

The if statement is Θ(1). The for loop is Θ(n). It seems to me that the recursive function calls are Θ(log n). My understanding is that I would add up the Thetas, and the highest order (Θ(n)) would survive, and the segment of code is order Θ(n). Is my understanding correct?

>Solution :

No. Consider:

1. Go through N values
2. Repeat for N/2 values
3. Repeat for N/2 values

We can rewrite that as:

1. Go through N values
2. Repeat for N values

If it were not recursive that’d just be 2N → Θ(n)…

but since it is recursive you repeat things N times, so it is:

Θ(n²)

BTW, it is Big-Θ since the upper bound (Big-O) and lower bound (Big-Ω) are the same.