The first loop will do a constant time operation exactly n
times. Therefore it is O(n)
.
The second loop (starting from i = 1
not i = 0
, you had a typo that I fixed) executes its body for i
set to 1, 4, 16, 64, ... that is, 4^0, 4^1, 4^2, 4^3, ... up until n
.
4^k < n
when k < log_4(n)
. Therefore the body of the second loop executes O(log(n))
times, because log base 4 and log base e differ by only a constant coefficient.