^ introduction

^ algorithm

^ question

Thx in advance!

4 Nuts and bolts This problem builds on your tutorial problem for week 7. You have to sort a bag of n nuts and n bolts by size, producing an output of n (nut, bolt) pairs that fit together. In part because the sizes are similar, and in part because you also want to watch videos while sorting, you are not relying on eyesight as you do this. So, the only way that you can tell if a particular bolt fits a particular nut is by trying to thread the bolt into the nut. You realize that you might be able to accomplish the task efficiently by using nuts and bolts that you match as a way to filter the rest. The following algorithm captures this idea. Algorithm NB-Quick(Nut-Set, Bolt-Set) If Nut-Set is empty, then Return the empty set Else If Nut-Set contains exactly one mt, say N, then Let B be the single bolt in Bolt-Set Return [(N, B)) Else Remove a nut, say N, from Nut-Set Partner-found False Tried-Bolts-0 While not Partner-found Remove any bolt, say B, from Bolt-Set If bolt B threads into nut N then Partner-found True Elsc Add B to Tricd-Bolts For cach nut in Nut-Set If the nut is too loose for B Add it to the set Loose-Nuts Else add it to the set Tight-Nuts For cach bolt in Boli-Set U Tried-Bolts If the bolt is too large for N Add it to the set Large-Bolts Else add it to the set Small-Bolts This work is licensed undder a Creative Commons Auribution NonCommercial 40 luternationall Por licease purpones, the author is the Univenity of British Columbia Return ((N, B)JU NB-Quick Loose-Nuts, Large-Bolts) U NB-Quick(Tight-Nuts, Small-Bolts) 1. Consider the case where, at every recursive call, both of the sets Tight-Nuts and Loose-Nuts have size in the range In/k, (k-I)m/k], for some integer k > 2. Write a recurrence relation for the running time of this algorithm. when n- 0or n I // base eases T(n) S //recursive case 2. Solve your recurrence to get a good asymptotic (big-O) upper-bound on the running time of this algorithm, as a function of both n and k