Time Complexity 0.25 * n and k +=k

Question

j = 1
while (j < n) {
    k = j
    while (k < n) {
        Sum += a[k] * b[k]
        k += k
    }
     j += 0.25 * n
}

From midterm practice

Answer 1

I came to the answer 0(logn) because

The outerloop will run exactly 4 times because they add 25 percent of n to j each iteration.

n = k * (n/4)

4(n/n) = k

4 = k = O(4)

The inner loop will run n times the first iteration because k will = 1.  However, on the second iteration k will equal 25 percent of n meaning it will only take 2 times to complete (25 + 25)  and (50 +50).  

The first iteration of k +=k is the same thing as saying k = k*2.  

We can solve this by solving the algorithm n = ((1 * 2) * 2) * 2 .... = 2^k

n = 2^k

k = log[2,n]

As a result the only iteration that isn't a constant time complexity is the first of the inner loop giving a O(logn) total cost.

Answer 2

j=kn

n totally