Cryptography Reference
In-Depth Information
Figure 3-1 The running time of algorithms for order O ( n ) (linear and polynomial), O (4e ln n ln ln n ) (subexponen-
tial), and O (2 n ) (exponential) for various values of n.
There is also another way to analyze an algorithm: by its storage complexity. Storage complexity is, for most
of the algorithms we are considering, not too much of a concern. However, requiring large amounts of storage
can quickly become a problem. For example, we could just pre-compute the factors for all numbers up to some
extremely large value and store this, and then we would have a very small running time (only as long as it takes
to search the list) for finding the factors of a number. However, the pre-computation and storage requirements
make this technique silly.
We will see this kind of concept used in a more clever way in Chapter 5.
3.2.1 Notation
There is another important notion in understanding algorithms: writing them out clearly, and unambiguously.
For doing so, authors typically take one of three approaches: picking a programming language du jour to write
all examples in,inventing aprogramming language, orwriting everything invariousformsofpseudocode (writ-
ing out the instructions in some mesh of natural language and a more formal programming language).
The first approach, picking a popular or well-known language, has an obvious disadvantage in that it dates
a topic immediately: a topic written 40 years ago might have used FORTRAN or ALGOL to implement its al-
gorithms, which would be difficult for many readers to understand. The second approach can be all right, but it
requires that the reader learn some language that the author thinks is best. This approach can have mixed results,
with some readers distracted so much by learning the language that they do not comprehend the text.
The final approach is often used, especially in abstract topics. While usually very clear, it can sometimes be
a challenge for a programmer to implement, especially if important details are glossed over.
The approach we use in this topic is to have a combination of pseudocode and writing out in an actual pro-
gramming language. The pseudocode in this and the following chapters is very simple: I merely state how a
program would operate, but in mostly plain English, instead of some abstract notation. The intent of this topic
is not to alienate readers, but to enlighten.
For some examples, I will like a reader to be able to easily see an algorithm in action and to have some
kind of source code to analyze and run. When these situations arise, I implement in a language that, in my
opinion, has a complete, free version available over the Internet; is easy to read even if the reader is not flu-
 
Search WWH ::




Custom Search