Analyze the time complexity of this program

Question

j = 1
while (j < n) {
  k = j
  while (k < n) {
    if (random() < 0.5) {
      k += 0.50 * log n
    } else {
      k += 0.25 * log n
    }
  }
  j += 0.1 * sqrt(n)
}

Answer 1

To analyze the time complexity of the provided code, let's examine each component:

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 will be approximately n / (0.1 * sq(n)​, which simplifies to 10 * sq(n)​.

2. Inner Loop (k Loop): The loop variable k starts at j (which is less than n) and increases by either 0.50×log⁡(n) or 0.25×log⁡(n) in each iteration. The exact increase depends on a random condition, but on average, it can be considered as 0.375×log⁡(n) per iteration (the average of 0.50 and 0.25). The number of iterations for the inner loop will be approximately n / (0.375 * log(n))

3. Overall Complexity: Since the inner loop is nested within the outer loop, the total time complexity is the product of the number of iterations of each loop. This gives us: 10 * sq(n)​ * n / (0.375 * log(n)) == 26.67 * (n)^1.5 / log(n).

Therefore, the time complexity of the given code can be approximated as (n)^1.5 / log(n)

Answer 2

Inner loop: If inner loop execute m times, then each of the brach execute m/2 times. Then , the k=1+(1/2)*(m/2)*logn + (1/4)*(m/2)*logn.  The inner loop teminate at k>=n , we can get m>=(8/3)*(n-1)/logn. So the inner loop time complexity is O(n/logn). The overall time complexity is O(sqrt(n)*n/logn).