How come the 3rd for loop complexity is O(nlogn)?


#1

how come the 3rd for loop complexity is O(nlogn) ??


#2

Firstly its O(logn) and not O(nlogn) assuming loop body is O(1). Now coming to how it is O(logn). You can think of it as a loop starting from 2^0 to 2^j such that 2^j>=n and value of j is being incremented by 1. Now loop will terminate when j>=log(n)[Base 2], hence it is O(logn).


#3

one might help himself with understanding of logarithms


#4

2^x = n
log(n) = x*log(2)
x = log(n) with base 2