Complexity Theory Illustrations

Page #633 of Chapter: Crypto-for-the-rest-of-us

level indicator

****

Case in point: Imagine that you sorted out 100 people by their height. Now another person comes in, and you need to fit him in the proper place in the sorted out list. How much effort will be required to do so?

Procedure A: check the new person against the shortest person on the list. If he is taller, then check him against the 2nd shortest, then the 3rd shortest until you find where to fit him.

Procedure B: you check the new person against the 50th person in the list. The results points to some 50 or 49 spots where the new comer coulld be fit. You repeat: comparing the new person against the middle of the new list, and so on. Until you fint the spot.

Procedure A may require one step, at most 100 steps, and on average 50 steps.
Procedure B always takes 7 steps.
in general for the case of n items Procedure A taks on average n/2 steps, and Procedure B -- much more efficient -- takes log(n) steps.

If we think the adversary needs to exercise procedure A, and so rate our complexity, then we lose because our adversary may be smart enough to find procedure B and steal our complexity.

Sometimes to fit another person in a previous list might be even more complex like the list of optimum itinerary for the traveling salesman.

* Version CE-H6703 (SERVER) Crypto Academy