O(nlogn) is the solution for me!


#1

We are analysing asymptotic behavior so N should be a large input, therefore the outer loop has to be include in that analysis, for me the complexity is O(nlogn)


#2

try to think this way:
for the first iteration of the outer loop, the inner loop need to run N times, the second iteration of the outer loop, the inner loop need to run N/2 times, third iteration, N/4 times, so add them up, you’ll get N + N/2 + N/4 + … + 1, which is 2N-1, and asymptoticly O(N)