Big O for specific double for loop

Question

public void f7(int N) {
    for (int i = N / 2; i > 0; i--) {
        if (i % 2 == 0) {
            for (int j = 0; j < N; j += 2) {
                System.out.println("Hey");
            }
        } else {
            for (int j = 1; j < N; j *= 2) {
                System.out.println("You");
            }
        }
    }
}

So I'm trying to find the asymptotic complexity (Big O) for this specific code block.

My thinking: the first for loop is O(N), and because half the time the number will be odd and the other half of the time it'll be even, it's still O(N) for the for loop inside the if statement, and O(Log N) for the for loop inside the else statement because of the j *= 2. So for my final answer I got O(N^2(Log N)), but apparently the answer is just O(N^2). I was wondering if anyone could explain where I'm going wrong in my thinking? Thanks!

Answer 1

The O(Log N) running time of the inner loop is only correct for odd values of i (which are half of the possible values of i). For even values of i, the inner loop will have a running time of O(N), since j is incremented by 2 in each iteration.

So what you have is

(N/4 * N/2) + (N/4 * log(N)) 
  even i          odd i

which is O(N²), since the first term (which asymptotically is the faster growing term) is N²/8, which asymptotically is O(N²).