Nested loop analysis, outer loop grows by sqrt n, inner randomly

Question

j = 1

while (j < n) {

  k = j

  while (k < log n) {

    if (random() < 0.5) {

      k += k

    } else {

      k += 1

    }

  }

  j += 0.1 * sqrt(n)

}

Answer 1

Mathematically:

The algorithm comprises an outer loop, executing approximately c * sqrt(n) times (where c is a constant). The inner loop is conditional on k (also denoted as j) being less than log(n). To determine the minimum number of outer loop iterations where the inner loop runs at least once, we solve the inequality 1 + t * 0.1 * sqrt(n) < log(n), yielding t = (log(n) - 1) / (0.1 * sqrt(n)).

The inner while loop is probabilistic due to the presence of the random() function and runs approximately c * loglog(n) times (where c is a constant). Consequently, the overall time complexity is t * c * loglog(n) + (c * sqrt(n) - t) * 1, and the dominant term in the equation is sqrt(n). Therefore, the time complexity is O(sqrt(n)).

Alternatively/Simply:

we know that log(n) = o(n^0.000...1) that is log grows slowly in comparison to any power of n(epsilon). so if we take large values of n say 10^10 the inner while loop executes only in the first iteration and in the later iterations as we can see k becomes greater than log(n) .So for large values of n only the outer loop iterations matter which is c*sqrt(n) , Hence the time complexity is O(sqrt(n)).

Comments

Shouldn't the time complexity of the inner loop be O(log n) in the worst case (k += 1)?

---

No, if it is logn then that function is not called as random function :(

Answer 2

The inner loop runs log(n) times, as we can consider the worst possible outcome of the if statement never being true, so k will increment by 1 and run till it reaches log(n).

The outer loop runs n / (0.1 * sqrt(n)) times, 

simplifying that we get n * 10 / sqrt(n).     ... (1)

Now consider very very large values of n, such as when n = 10^100million

When n = 10^100million, it will run 

(10^100million * 10) / sqrt(10^100million)      ... [From (1)]

10^100,000,001/sqrt(10^100million)              ... [multiplying that 10 with 10^100mill]

(10^100,000,001)/10^10,000

 = 10^99,990,001

The outer loop runs 10^99,990,001 times when n = 10^100 million.

By this result, it must always have an upper bound of O(n), i.e. it will never run more than O(n) times.

Hence, the time complexity is O(n. log(n))

Not sure if it's correct, kindly confirm.

Answer 3

Here the j loop is incremented by 0.1*sqrt(n)

n-1/0.1*sqrt(n)

sqrt(n)  # Ignoring 1 and 0.1

So the time complexity of the j loop is O(sqrt(n))

The k loop might execute in O(1) time but assuming the worst case the time complexity is O(log n)

Hence the time complexity overall is O(sqrt(n)log(n))

Answer 4

Outer loop: n/0.1sqrt(n)=10sqrt(n), so the outer loop is O(sqrt(n)).
Inner loop: the inner loop contain a random(), which is 50% of the time smaller than 0.5 and 50% of the time larger than 0.5. Then, We can anticipate that the overall number of executions of the inner loop, denoted as m, will encompass an equal count of executions for both of its branches. For the exponential branch, we can calculate that the largest excution times is O(loglog(n)). For the linear branch, we can see that the largest excution times is O(log(n)).  Of course, it should take the smaller one: O(loglog(n)).
So the time complexity is O(sqrt(n)*loglog(n))

Answer 5

Let's analyze the time complexity:

1. Outer Loop (j Loop): The loop variable j starts at 1 and increases by 0.1 * sq(n) in each iteration. The number of iterations for the outer loop is approximately 10 * sq(n).

2. Inner Loop (k Loop): This loop runs until k is less than log⁡n. The increase in k depends on a random condition:

If random() < 0.5, k is doubled.Otherwise, k increases by 1.

The doubling of k will rapidly increase its value, reaching log⁡n in $O(\log \log n)$steps because doubling represents an exponential growth. The increment by 1 is less significant compared to the doubling and will not dominate the time complexity. Therefore, the average case for the inner loop is dominated by the case where k is doubled, giving us $O(\log \log n)$ iterations.

3. Overall Complexity: The total time complexity is the product of the number of iterations of each loop, which gives us:

10 * sq(n) * $(\log \log n)\; =\; O($sq(n) * $(\log \log n))$

Therefore, the time complexity of the given code can be approximated as $O($sq(n) * $(\log \log n).$