Extracting Upper Bound from this Loop with Multiplication Increment

Question

I understand how to use summation to extract the time complexity (and Big O) from linear for-loops using summation, but how would you use it for multiplication incremental loops to get O(logn). For example, the code below is O(nlogn), but I don't know why.

for (i = 0; i < n; i++)
 for (j = 1; j < n; j*7)
    /*some O(1) operations*/

Also, why is a while loop O(logn) and a do-while loop O(n^2).

Answer 1

At each iteration of the inner loop you perform j = j * 7 (I assume this is what you meant)

That is, at each iteration j = 7j

After n iterations, j = j*7*7*7*7*...*7*7 = j*(7 ^ n)

Let n be the number we want to reach and m the number of iterations, so:

n = j*7*7*7*...7 = j*(7 ^ m)

Let's take a log from both sides:

log(n) = log(j * (7 ^ m)) ~= m*log(7) = O(m)

So, as we can see - the inner loop runs O(log(n)) times.