Graphics Programs Reference
In-Depth Information
This means that, in general, the growth rate of the time complexity of
an algorithm with respect to input size is more important than the time com-
plexity for any fixed input. While this might not always hold true for specific
real-world applications, this type of measurement of an algorithm's efficiency
tends to be true when averaged over all possible applications.
0x721
Asymptotic Notation
Asymptotic notation
is a way to express an algorithm's efficiency. It's called
asymptotic because it deals with the behavior of the algorithm as the input
size approaches the asymptotic limit of infinity.
Returning to the examples of the 2
n
+ 365 algorithm and the 2
n
2
+ 5
algorithm, we determined that the 2
n
+ 365 algorithm is generally more
efficient because it follows the trend of
n
, while the 2
n
2
+ 5 algorithm
follows the general trend of
n
2
. This means that 2
n
+ 365 is bounded above
by a positive multiple of
n
for all sufficiently large
n
, and 2
n
2
+ 5 is bounded
above by a positive multiple of
n
2
for all sufficiently large
n
.
This sounds kind of confusing, but all it really means is that there exists a
positive constant for the trend value and a lower bound on
n
, such that the
trend value multiplied by the constant will always be greater than the time
complexity for all
n
greater than the lower bound. In other words, 2
n
2
+ 5 is
in the order of
n
2
, and 2
n
+ 365 is in the order of
n
. There's a convenient
mathematical notation for this, called
big-oh notation
, which looks like O(
n
2
)
to describe an algorithm that is in the order of
n
2
.
A simple way to convert an algorithm's time complexity to big-oh notation
is to simply look at the high-order terms, since these will be the terms that
matter most as
n
becomes sufficiently large. So an algorithm with a time
complexity of 3
n
4
+ 43
n
3
+ 763
n
+ log
n
+ 37 would be in the order of O(
n
4
),
and 54
n
7
+ 23
n
4
+ 4325 would be O(
n
7
).
0x730
Symmetric Encryption
Symmetric
ciphers are cryptosystems that use the same key to encrypt and
decrypt messages. The encryption and decryption process is generally faster
than with asymmetric encryption, but key distribution can be difficult.
These ciphers are generally either block ciphers or stream ciphers.
A
block cipher
operates on blocks of a fixed size, usually 64 or 128 bits. The
same block of plaintext will always encrypt to the same ciphertext block,
using the same key. DES, Blowfish, and AES (Rijndael) are all block ciphers.
Stream ciphers
generate a stream of pseudo-random bits, usually either one
bit or byte at a time. This is called the
keystream,
and it is XORed with the
plaintext. This is useful for encrypting continuous streams of data. RC4 and
LSFR are examples of popular stream ciphers. RC4 will be discussed in depth
in “Wireless 802.11b Encryption” on page 433.
DES and AES are both popular block ciphers. A lot of thought goes into
the construction of block ciphers to make them resistant to known crypt-
analytical attacks. Two concepts used repeatedly in block ciphers are confusion
