What is the time complexity of the following code

Question

int rand7()
{
    int vals[5][5] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}

This solution solves the problem listed in details here.

Answer 1

The worst-case running time will be infinite if you keep on getting i, j such that vals[i-1][j-1] == 0, so the while loop will never terminate. This situation almost surely does not happen though.

Let T denotes the expected running time of rand7(), we have the following observation:

• if i == 1, 2, 3, 4, then no matter what j is, we will have vals[i-1][j-1] != 0, so the while loop will iterate only once in this case; - This event occurs with probability 4/5
• if i == 5 and j == 1, then vals[i-1][j-1] != 0 and the while loop will iterate only once; - This event occurs with probability 1/25
• in the remaining cases we have vals[i-1][j-1] == 0, so we need to start over with new random values (i, j). - This occurs happens with probability 4/25

From the observation above, we have the following relationship:

T = 4/5 * 1 + 1/25 * 1 + 4/25 * (1 + T)

Therefore the expected running time is T = 25/21 = O(1).