A.3. Complexity theory
We should say a few words about what is meant by a problem being tractable or intractable. The key idea is, for a given algorithm to solve a particular problem, to examine how fast the amount of computation required typically grows with the size of the problem. Take for example Euclid’s algorithm for finding the gcd of two numbers, m and n. It can be shown that the number of steps required grows roughly as the log of larger of the two numbers. In fact we can go further and show that the worst case occurs when the input numbers are two successive Fibonacci numbers, in which case the number of steps is the Fibonacci index of the larger number. The Fibonacci numbers grow roughly exponentially with the golden ratio.
Euclid’s ...
Get The Modelling and Analysis of Security Protocols: the CSP Approach now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
