Question

Given a collection of n nuts, and a collection of n bolts, each arranged in an increasing order of size, give an O(n) time algorithm to check if there is a nut and a bolt that have the same size. You can assume that the sizes of the nuts and bolts are stored in the arraysNUTS[1..n] and BOLTS[1..n], respectively, where NUTS[1] < ··· < NUTS[n] and BOLTS[1] < ··· < BOLTS[n]. Note that you only need to report whether or not a match exists; you do not need to report all matches.

(When asked to give an algorithm that meets a certain time upper bound, you need to give the algorithm (pseudocode/description) and analyze its running time to show that it meets the required bound)

Answer 1

Following is the pseudocode algorithm:

matching_size(nuts[],bolts[],n) //nuts and bolts are arrays containing size of nuts and bolts in increasing order. n is the size of both

{

i=0,j=0; //we initialize two indexes to 0 to iterate through the array

while(i<n and j<n)

{

if(nuts[i]<bolts[j])

i=i+1;

else if(bolts[i]<nuts[j])

j=j+1;

else //if sizes are equal

return true;

}

return false; //if program reaches this point, no match was found

}

Time complexity analysis:

In the best-case scenario, the first elements of both arrays will be equal and only 1 comparison will take place. So best-case is O(1).

In the worst-case scenario, the arrays will have alternating increasing elements and will take 2n comparisons. So worst-case is O(n).

So, overall time complexity is O(n).