Estimate:High
Explanation: The number of instructions in each iteration of the outer loop is about 200 if we assume that the key is found in the last lookup.