L>А дальше получаем, что имеем дело с O(log(1)) + O(log(2)) + .. + O(log(N-1)) + O(log(N)) = O(log(N))

Ох
O(N*log(N)) получается как ни крути

По вашей логике выходит тогда
1+2+3+...+N=O(N) — что сильно не так