Presumingly simple runtime analysis, need explanation

Question

According to todays lecture, the first loop has a runtime of the order O(n), while the second loop has a runtime of the order O(log(n)).

for (int i = 0; i < n; i++) { // O(n)
    stuff(); // O(1)
}

for (int i = 1; i < n; i*=4) { // O(log(n))
    stuff(); // O(1)
} 

Could someone please elaborate on why?

Answer 1

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.

Answer 2

Time complexity is calculated in terms of how the numbers of times all unit time statements in the code are executed as function of n (input size.)

1. Input size = n and for loop runs in O(N) and stuff runs of O(N)*O(1) hence overall O(N)

2. for loop runs till 4^k-1 < n where k is number of iterations. Taking log on both sides of inequality we get (k-1)*log4 < logn, k < logn/log4 +1, k=O(logn) because log4 is constant. Stuff runs in O(logn)*O(1) hence overall O(logn)