When the iterations of the inner loop depend on the outer loop, it's better to sum over the amount of iterations of the inner loop. There is no need to overcomplicate this and think of logarithms just because the outer loop has logarithmic behavior.
Iterations
In this example, we can see the number of iteration the inner loop performs is halved in each step of the outer loop:
- $N$ iterations of the inner loop
- $\frac{N}{2}$ iterations
- $\frac{N}{4}$ iterations
- $\dots$
- $\frac{N}{2^i}$ iterations
- $\dots$
- 1 iteration
as the outer loop iterates.
Formalizing
Factoring $N$, we get:
$$ N(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{N})$$
Knowing that:
$$\sum_{i=0}^\infty \frac{1}{2^i} = 1 + \frac{1}{2}+ \frac{1}{4}+ \frac{1}{8}+\cdots = 2$$
we can conclude that:
$$ N(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{N}) < 2N$$
Which is why the algorithm's complexity is bounded by $\mathcal{O}(N)$
Since the algorithm performs at least $N$ steps (assuming $N \geq 1$), it follows that the runtime behavior is also described by $\Omega(N)$, which implies that it is in $\Theta(N)$