Randomized Algorithm - Basics (4 Questions in 1)

Question

What is the time complexity of this algorithm

for i = 1 to n {
    if random() > 0.5 {
        exit()    // This is question option a.
                  // There are 3 other questions, where this statement is replaced by
                  // b.  i = i + 1
                  // c.  i = i - 1
                  // d.  i = 2 * i
    }
}

Assume that random() returns a number uniformly in the 0 to 1 range.

Answer 1

a. Noticing that the random only takes a half chance to terminate the whole loop on each loop, therefore the loop has a chance to run n times, also noticing that the loop can NEVER run more than n times, the time complexity should be O(n).

b. Same as above, the loop can end faster but not any slower than n times, therefore the time complexity should be O(n) too.

c. In this case the loop has a chance to go slower (and much slower) than O(n). Each loop has a 50% chance "doesn't count", so the time complexity is Ω(n). We can't express the complexity in big O notation because no matter how we choose the k as the constant, there is still a chance that the loop goes forever and goes beyond the kf(n) expression.

d. Same as a) and b), the time complexity is O(n).

This answer treats "time complexity" as finding the worst case time complexity.

The average case time complexity is left for practice :)

Answer 2

Option a: exit()

The given code runs a loop 'n' times, similar to flipping a coin at each iteration. If the coin shows heads (say, random() > 0.5), the program stops. In the worst case, it takes O(n) time, but it might finish earlier if the loop exits before 'n' iterations.

Option b: i = i + 1

The actual time complexity may vary due to the random(). In some cases, it might terminate early, and in others, it might run for the full of n iterations. On average, the loop will iterate approximately n/2 times because the random() function that generates values uniformly in the 0 to 1 range, and there's a probability of 0.5 that the condition will be true. Therefore, the expected time complexity is proportional to O(n).

Option c: i = i - 1

Similar to above condition(b) the average time complexity of this could be O(n). However, in some cases this may lead to an infinite loop if the condition consistently leads to i being decremented.

Option d: i = 2 * i

In the worst case, where the loop condition always evaluates to true due to the randomness of `random()`, the loop may iterate n times, resulting in a time complexity of (O(n)).

On average, the loop might double the variable i with iteration, and the loop will execute until 2^k >= n, where k is the number of iterations. On solving k = log₂n, yielding an average time complexity of O(log n).