1. Informal Introduction
2. O-notation
3. Omagha -notation
4. 0-notation
5. Useful Property Involving the Asymptotic Notations
6. Using Limits for Comparing Orders of Growth
7. Basic Efficiency Classes
8. Exercises

**Asymptotic
Notations and Basic Efficiency Classes**

*1. Informal Introduction*

*2. O-notation*

*3. Omagha -notation*

*4. 0-notation*

*5. Useful Property Involving the Asymptotic
Notations*

*6. Using Limits for Comparing Orders of Growth*

*7. Basic Efficiency Classes*

*8. Exercises*

As
pointed out in the previous section, the efficiency analysis framework
con-centrates on the order of growth of an algorithm’s basic operation count as
the principal indicator of the algorithm’s efficiency. To compare and rank such
orders of growth, computer scientists use three notations: ** O** (big oh), (big omega), and (big
theta). First, we introduce these notations informally, and then, after
sev-eral examples, formal definitions are given. In the following discussion,

**Informal
Introduction**

Informally,
** O(g(n))** is the set of all functions with
a lower or same order of growth as

Indeed,
the first two functions are linear and hence have a lower order of growth than ** g(n)** =

Indeed,
the functions *n*^{3} and
0.00001*n*^{3} are both
cubic and hence have a higher order of growth than *n*^{2}** ,** and so has the fourth-degree
polynomial

The
second notation, ** (g(n)),** stands for the set of all
functions with a higher or same order of growth as

Finally, ** (g(n))** is the
set of all functions that have the same order of growth as

Hopefully,
this informal introduction has made you comfortable with the idea behind the
three asymptotic notations. So now come the formal definitions.

*O***-notation**

**DEFINITION
**A
function** t (n) **is said
to be in

** t (n) **≤

The
definition is illustrated in Figure 2.1 where, for the sake of visual clarity, ** n** is extended to be a real number.

As an
example, let us formally prove one of the assertions made in the introduction:
100** n** + 5 ∈

100** n** + 5 ≤ 100

Thus, as
values of the constants ** c** and

Note that
the definition gives us a lot of freedom in choosing specific values for
constants ** c** and

100** n** + 5 ≤ 100

to
complete the proof with ** c** = 105 and

**Ω****-notation**

**DEFINITION
**A
function** t (n) **is said
to be in

** t (n) **≥

The
definition is illustrated in Figure 2.2.

Here is
an example of the formal proof that *n*^{3} ∈ * (n*^{2}** )**:

*n*^{3}** **≥

i.e., we
can select ** c** = 1 and

**DEFINITION
**A
function** t (n) **is said
to be in

*c*_{2}** g(n) **≤

The
definition is illustrated in Figure 2.3.

For
example, let us prove that _{2}^{1}** n(n** − 1

Second,
we prove the left inequality (the lower bound):

**Useful
Property Involving the Asymptotic Notations**

Using the
formal definitions of the asymptotic notations, we can prove their general
properties (see Problem 7 in this section’s exercises for a few simple
examples). The following property, in particular, is useful in analyzing
algorithms that comprise two consecutively executed parts.

**THEOREM** If *t*_{1}** (n)** ∈

*t*_{1}** (n) **+

(The
analogous assertions are true for the and notations as well.)

**PROOF** The proof extends to orders
of growth the following simple fact about

four
arbitrary real numbers *a*_{1}*, b*_{1}*, a*_{2}*, b*_{2}: if *a*_{1} ≤ *b*_{1} and *a*_{2} ≤ *b*_{2}** ,** then

Since *t*_{1}** (n)** ∈

*t*_{1}** (n) **≤

Similarly,
since *t*_{2}** (n)** ∈

*t*_{2}** (n) **≤

Let us
denote *c*_{3} = max{*c*_{1}*, c*_{2}} and consider ** n** ≥ max{

*t*_{1}** (n) **+

*c*_{3}*g*_{1}** (n) **+

*c*_{3}2 max{*g*_{1}*(n), g*_{2}** (n)**}

Hence, *t*_{1}** (n)** +

So what
does this property imply for an algorithm that comprises two consec-utively
executed parts? It implies that the algorithm’s overall efficiency is
deter-mined by the part with a higher order of growth, i.e., its least
efficient part:

For
example, we can check whether an array has equal elements by the following
two-part algorithm: first, sort the array by applying some known sorting
algorithm; second, scan the sorted array to check its consecutive elements for
equality. If, for example, a sorting algorithm used in the first part makes no
more than _{2}^{1}** n(n** − 1

**Using
Limits for Comparing Orders of Growth**

Though
the formal definitions of *O, ***ѳ**** ,** and

Here are
three examples of using the limit-based approach to comparing orders of growth
of two functions.

**EXAMPLE 1 **Compare
the orders of growth of** **_{2}^{1}** n(n **−

Since the
limit is equal to a positive constant, the functions have the same order of
growth or, symbolically, _{2}^{1}** n(n** − 1

Thus,
though 2**^{n}** grows very fast,

**Basic
Efficiency Classes**

Even
though the efficiency analysis framework puts together all the functions whose
orders of growth differ by a constant multiple, there are still infinitely many
such classes. (For example, the exponential functions ** a^{n}** have
different orders of growth for different values of base

You could raise a concern that classifying algorithms by their asymptotic effi-ciency would be of little practical use since the values of multiplicative constants are usually left unspecified. This leaves open the possibility of an algorithm in a worse efficiency class running faster than an algorithm in a better efficiency class for inputs of realistic sizes. For example, if the running time of one algorithm is n3 while the running time of the other is 106n2, the cubic algorithm will outperform the quadratic algorithm unless n exceeds 106. A few such anomalies are indeed known. Fortunately, multiplicative constants usually do not differ that drastically. As a rule, you should expect an algorithm from a better asymptotic efficiency class to outperform an algorithm from a worse class even for moderately sized inputs. This observation is especially true for an algorithm with a better than exponential running time versus an exponential (or worse) algorithm.

Exercises 2.2

Use the most appropriate notation among O, **Ω**, and **ѳ **and to indicate the time efficiency class of sequential search (see Section 2.1)

in the worst case.

in the best case.

in the average case.

Use the informal definitions of O, **Ω**, and **ѳ **to determine whether the follow-ing assertions are true or false.

4 a. Table 2.1 contains values of several functions that often arise in the analysis of algorithms. These values certainly suggest that the functions

are listed in increasing order of their order of growth. Do these values prove this fact with mathematical certainty?

Prove that the functions are indeed listed in increasing order of their order of growth.

5 List the following functions according to their order of growth from the lowest to the highest:

b.Prove that exponential functions a-power(n) have different orders of growth for different values of base a > 0.

7 Prove the following assertions by using the definitions of the notations in-volved, or disprove them by giving a specific counterexample.

** **8 Prove the
section’s theorem for

**a.** **ѳ** notation. **b.** **Ω**notation.

** **9**
**We mentioned in this section that one can check
whether all elements of an array are distinct by a two-part algorithm based on
the array’s presorting.

**
**If the presorting is done by an algorithm with a
time efficiency in ** (n** log

**
**If the sorting algorithm used for presorting needs
an extra array of size ** n,** what
will be the space-efficiency class of the entire algorithm?

** **10 ** **The ** range** of a finite nonempty set of

**
**An unsorted array

**
**A sorted array

**
**A sorted singly linked list

**
**A binary search tree

**
**

** **11** ***Lighter
or heavier? *You have* **n >** *2
identical-looking coins and a two-pan* *balance
scale with no weights. One of the coins is a fake, but you do not know whether
it is lighter or heavier than the genuine coins, which all weigh the same.
Design a ** (**1

**
*** 12 Door in a wall *You are
facing a wall that stretches infinitely in both direc-tions. There is a door in
the wall, but you know neither how far away nor in which direction. You can see
the door only when you are right next to it. De-sign an algorithm that enables
you to reach the door by walking at most ** O(n)** steps
where

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Fundamentals of the Analysis of Algorithm Efficiency : Asymptotic Notations and Basic Efficiency Classes |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.