CODEWITHSUNDEEP
algorithmtime-complexityrecurrence
Wazowski
Wazowski

Reputation: 3

Time complexity recurrence relation

I need to find the recurrence relation:

int search(int[] a, int l, int h, int goal) { 
    if (low == high) return 0; 
    int tg = target(a, l, h); 
    if (goal < target) 
        return search(a, l, tg-1, goal); 
    else if (goal > target) 
        return search(a, tg +1, h, goal); 
    else 
        return a[tg];
}

What would be the initial way to approach this question? I'm not asking for a solution, but just an initial way to approach it. Thanks!

Upvotes: 0

Views: 211

Answers (1)

pkacprzak
pkacprzak

Reputation: 5629

Since you are not asking about an exact solution (however, I can provide that if you want), I'm going to give you a hint, which is a very simple, yet not a well-known method of approaching such problems.

The crucial idea is to modify your function to a function which has probably worst complexity, but its expected complexity can be measured easily, let's call this modified function findTarget2:

public static int findTarget2 (int[] a, int low, int high, int goal) { 
    if (low == high) return 0;
    int len = high - low + 1; //length of the array range, i.e. input size
    while (true) { 
       int target = selectTarget(a, low, high); 
       if (goal < target && target-low <= 3/4 * len) 
          return findTarget2(a, low, target-1, goal); 
       else if (goal > target && high-target <= 3/4 * len) 
          return findTarget2(a, target+1, high, goal); 
       else if (goal == target)
          return a[target];
    }

}

Now, let f(n) be the time complexity of the original, and g(n) be the time complexity of the findTarget2 function, where n is the size of their input, i.e. the length of the array range equal high-low+1.

Now, let's say that selectTarget results in a bad execution if and only if it doesn't cause any return call inside the while's body.

The first observation is that g(n) >= f(n), because in a case of a bad execution, findTarget2 basically calls itself on the same input, while the original function reduces the size of input by at least 1. Thus, if have an upper bound for g(n), then the same bound applies to f(n).

Next, the expected time complexity of g(n) can be written as follows:

EX[g(n)] <= EX[g(3/4 * n) + X * O(n)]

which can be written as follows using linearity of expected value:

EX[g(n)] <= EX[g(3/4 * n)] + EX[X] * O(n)

where X is the random variable denoting the number of while loop executions until it results in return call, and the last O(n) is the non-recursive time spent in findTarget2 function, and it's O(n), because it is said that selectTarget function runs in that time.

Now your task is just to compute EX[X] and then you can use Master theorem to get the final expected time complexity of g(n), which is also an upper bound for the expected time complexity of f(n), so the upper bound of the complexity of the original function.

Upvotes: 1

Related Questions