2.2- Asymptotic Notation/ Basic Efficiency Classes

Question 1

To compare and rank such orders
of growth, computer scientists use three notations:

Answer 1

O (big oh), (big omega), and (big theta).

Question 2

Class: 1
Constant

Answer 2

Short of best-case efficiencies, very few reasonable
examples can be given since an algorithm’s running
time typically goes to infinity when its input size grows
infinitely large.

Question 3

Class: log n
logarithmic

Answer 3

Typically, a result of cutting a problem’s size by a
constant factor on each iteration of the algorithm (see
Section 4.4). Note that a logarithmic algorithm cannot
take into account all its input or even a fixed fraction
of it: any algorithm that does so will have at least linear
running time.

Question 4

Class: n
linear

Answer 4

Algorithms that scan a list of size n (e.g., sequential
search) belong to this class.

Question 5

Class: n log n
linearithmic

Answer 5

Many divide-and-conquer algorithms (see Chapter 5),
including mergesort and quicksort in the average case,
fall into this category

Question 6

Class: n^2
quadratic

Answer 6

Typically, characterizes efficiency of algorithms with
two embedded loops (see the next section). Elementary sorting algorithms and certain operations on n × n matrices are standard examples.

Question 7

Class: n^3
cubic

Answer 7

Typically, characterizes efficiency of algorithms with
three embedded loops (see the next section). Several
nontrivial algorithms from linear algebra fall into this
class.

Question 8

Class: 2^n
exponential

Answer 8

Typical for algorithms that generate all subsets of an
n-element set. Often, the term “exponential” is used
in a broader sense to include this and larger orders of
growth as well.

Question 9

Class: n!
factorial

Answer 9

Typical for algorithms that generate all permutations
of an n-element set.