3.2. Complexity Issues

Given an algorithm (or an implementation of the same), the time and space required for the execution of the algorithm on a machine depend very much on the machine’s architecture and on the compiler. But this does not mean that we cannot make some general theoretical estimates. The so-called asymptotic estimates that we are going to introduce now tend to approach the real situation as the input size tends to infinity. For finite input sizes (which is always the case in practice), these theoretical predictions turn out to provide valuable guidelines.

3.2.1. Order Notations

We start with the following important definitions.

Definition 3.1.

Let f and g be positive real-valued functions of natural numbers.

  1. f is said to be ...

Get Public-key Cryptography: Theory and Practice 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.