outer loop until log n, inner loop exponential increase

Question

Given:

int j = 5

while (j < log n) {

      int k = 5

      while (k < n) {

            Sum += a[j]*b[k]

            k = k^1.3

      }

      j = 1.3 * j

}

Answer 1

My analysis:

Outer loop:

if it runs k times, then 1.3^k= log n -> k = log log n

O(log log n)

Inner loop increases:

k^1.3 -> (k^1.3)^1.3 -> ... -> k^1.3^z

O(log log n)

Combined would be:

O((log log n)^2)

Answer 2

Inner Loop:
k runs till n and k = k^1.3 in every iteration

=> k, k^1.3, k^1.3^1.3, k^1.3^1.3^1.3..... k^1.3^x

equating it to n, we get x = O(log log n).

Outer Loop: 

j runs till log n and j = 1.3 *j in every iteration 

=> j, j*1.3, j*1.3*1.3, .... j*1.3^x

equating it to log n, we get x = O(log log n).

Time Complexity = O((log log n)^2)

Answer 3

Outerloop:

j will run from 5, 5*(1.3), 5*(1.3)^2......5*(1.3)^m.

5*(1.3)^m = logn (outer loop will run till this condition satisfy)

That is m = log(log n) --> Apply log on both sides in the above equation.

Innerloop:

k will run from 5, 5^1.3, 5^(1.3)^2......5^(1.3)^m.

5^(1.3)^m = n (inner loop will run till this condition satisfy)

That is m = log(log n) --> Apply log on both sides in the above equation.

Here the loops are nested so just multiply both outer and inner loop complexity which gives O(log(logn))^2

Answer 4

1. Let the inner loop run x time

Since k = k^1.3 while k < n:     

5^{(1.3)^x} = n

log₅ n = 1.3^x

x = log_1.3log₅ n

After ignoring the constants, the running time of the inner loop is loglog n

2. Let the outer loop run y time

Since j = 1.3 * j while j < log n:

5 * 1.3^y = log n

1.3^y = (log n) / 5

y = log_1.3 (log n) / 5

After ignoring the constants, the running time of the outer loop is loglog n

3. Since the inner loop runs loglog n times in each iteration of the outer loop, the overall running time is:

loglog n * loglog n = log(log(n)) log(log(n)) = O(log²(log(n)))