Chapter 3

Algorithms

© 2019 McGraw-Hill Education. All rights reserved. Authorized only for instructor use in the classroom. No reproduction or further distribution permitted without the prior written consent of McGraw-Hill Education.
 Section 3.1
Algorithms

© 2019 McGraw-Hill Education

 Problems and Algorithms
In many domains there are key general problems that
ask for output with specific properties when given
valid input.
The first step is to precisely state the problem, using
the appropriate structures to specify the input and
the desired output.
We then solve the general problem by specifying the
steps of a procedure that takes a valid input and
produces the desired output. This procedure is called
an algorithm.
An algorithm is a finite set of precise instructions for
performing a computation or for solving a problem.
© 2019 McGraw-Hill Education
 Properties of Algorithms
Input: An algorithm has input values from a specified set.
Output: From the input values, the algorithm produces
the output values from a specified set.
Definiteness: The steps of an algorithm must be defined
precisely.
Correctness: An algorithm should produce the correct
output values for each set of input values.
Finiteness: An algorithm should produce the output after
a finite number of steps for any input.
Effectiveness: It must be possible to perform each step of
the algorithm correctly and in a finite amount of time.
Generality: The algorithm should work for all problems of
the desired form.
© 2019 McGraw-Hill Education
 Example
Describe an algorithm for finding the maximum value
in a finite sequence of integers.
Solution: Perform the following steps
1. Set the temporary maximum equal to the first
integer in the sequence.
2. Compare the next integer in the sequence to the
temporary maximum. If it is larger than the
temporary maximum, set the temporary maximum
equal to this integer.
3. Repeat step 2 if there are more integers. If not, stop.
4. When the algorithm terminates, the temporary
maximum is the largest integer in the sequence.
© 2019 McGraw-Hill Education
 Pseudocode
Algorithms can be specified in pseudocode.
Pseudocode is an intermediate step between an
English language description of an algorithm and an
implementation of this algorithm in a programming
language.
procedure max(a1, a2, …., an: integers)
max := a1
for i := 2 to n
if max < ai then max := ai
return max{max is the largest element}

Does this algorithm have all the algorithm properties?

© 2019 McGraw-Hill Education
 Searching Problems
The general searching problem is to locate an element x
in the list of distinct elements a1,a2,...,an, or determine
that it is not in the list.
The solution to a searching problem is the location of
the term in the list that equals x (that is, i is the
solution if x = ai) or 0 if x is not in the list.
We will study two different searching algorithms:
linear search and binary search.

© 2019 McGraw-Hill Education

 Linear Search
First compare x with a1. If they are equal,
return the position 1.
If not, try a2. If x = a2, return the position 2.
Keep going, and if no match is found when the
entire list is scanned, return 0.
procedure linear search(x: integer,
a1, a2, …,an: distinct integers)
i := 1
while (i ≤ n and x ≠ ai)
i := i + 1
if i ≤ n then location := i
else location := 0
return location {location is the subscript of the term ai
that equals x, or is 0 if x is not found}
© 2019 McGraw-Hill Education
 Binary Search 1

Assume the input is a list of items in increasing order.

The algorithm begins by comparing the element to be
found with the middle element.
1. If the middle element is lower, the search proceeds
with the second half of the list.
2. If it is not lower, the search proceeds with the
first half of the list (through the middle position).
3. Repeat this process until we have a list of size 1.
4. If the element we are looking for is equal to the
element in the list, the position is returned.
5. Otherwise, 0 is returned to indicate that the
element was not found.
© 2019 McGraw-Hill Education
 Binary Search 2

procedure binary search(x: integer,

a1,a2,…, an: increasing integers)
i := 1 {i is the left endpoint of interval}
j := n {j is right endpoint of interval}
while (i < j)
m := ⌊(i + j)/2⌋
if x > am then i := m + 1
else j := m
if x = ai then location := i
else location := 0
return location {location is the subscript i of the term ai
equal to x, or 0 if x is not found}

© 2019 McGraw-Hill Education

 Binary Search 3

Example: The steps taken by a binary search for 19 in the list:

1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22
1. Since 19 > 10,
1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22
2. Since 19 > 16
1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22
3. Since 19 ≯ 19,
1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22
4. Since 19> 18,
1 2 3 5 6 7 8 10 12 13 15 16 18 19 20 22
5. Now the list has a single element and the loop ends.
Since 19=19, the location 14 is returned.

© 2019 McGraw-Hill Education

 Sorting
To sort the elements of a list is to put them in increasing
(or decreasing) order (numerical order, alphabetic).
A nontrivial percentage of all computing resources are
devoted to sorting different kinds of lists, especially
applications involving large databases of information
that need to be presented in a particular order.
An amazing number of fundamentally different
algorithms have been invented for sorting.
Their relative advantages and disadvantages have
been studied extensively.

© 2019 McGraw-Hill Education

 Bubble Sort 1

Bubble sort puts a list into increasing order by

successively comparing adjacent elements,
interchanging them if they are in the wrong order.

procedure bubble sort(a1,…,an: real numbers with n ≥ 2)

for i := 1 to n− 1
for j := 1 to n − i
if aj >aj+1 then interchange aj and aj+1
{a1,…, an is now in increasing order}

© 2019 McGraw-Hill Education

 Bubble Sort 2

Example: Show the steps of bubble sort with 3 2 4 1 5

© 2019 McGraw-Hill Education

 Insertion Sort 1

To sort a list with n elements, Insertion sort begins

with the 2nd element. It compares the 2nd element
with the 1st and puts it before the first if it is not larger.
Next the 3rd element is put into the correct position
among the first 3 elements.
In general, in the jth step of the insertion sort, the jth
element of the list is inserted into the correct position
in the list of the previously sorted j − 1 elements.
To insert the jth element in the list, a linear search
technique is used to find the correct position.

© 2019 McGraw-Hill Education

 Insertion Sort 2

procedure insertion sort(a1,…,an:

real numbers with n ≥ 2)
for j := 2 to n
i := 1
while (aj > ai)
i := i + 1
m := aj
for k := 0 to j − i − 1
aj-k := aj-k-1
ai := m
{Now a1,…,an is in increasing order}

© 2019 McGraw-Hill Education

 Insertion Sort 3

Example: Show all the steps of insertion sort with the

input: 3 2 4 1 5
i. 2 3 4 1 5 (first two positions are interchanged)
ii. 2 3 4 1 5 (third element remains in its position)
iii. 1 2 3 4 5 (fourth is placed at beginning)
iv. 1 2 3 4 5 (fifth element remains in its position)

© 2019 McGraw-Hill Education

 String Matching 1

Finding where a pattern occurs in a text string is called

string matching. For instance, we can ask whether the
pattern 101 can be found within the string 11001011.
String matching plays an essential role in a wide variety
of applications, including text editing, spam filters,
systems that look for attacks in a computer network,
search engines, plagiarism detection, bioinformatics,
and many other important applications.
Solving questions about the genome requires the use of
efficient algorithms for string matching, especially
because a string representing a human genome is about
3 × 109 characters long.
© 2019 McGraw-Hill Education
 String Matching 2

procedure string match (n, m: positive integers, m ≤ n,

t1, t2,… , tn, p1, p2,… , pm: characters)
for s := 0 to n − m
j := 1
while ( j ≤ m and ts+j = pj )
j := j + 1
if j > m then print “s is a valid shift”

© 2019 McGraw-Hill Education

 Homework

Exercises: 7, 9, 13, 25, 37, 41, 55

© 2019 McGraw-Hill Education

 Section 3.2
The Growth of Functions

© 2019 McGraw-Hill Education

 The Growth of Functions
In computer science, we want to understand how
quickly an algorithm can solve a problem as the
size of the input grows.
We can compare the efficiency of two different
algorithms for solving the same problem.
We can also determine whether it is practical to
use a particular algorithm as the input grows.

© 2019 McGraw-Hill Education

 Big-O Notation
Let f and g be functions from the set of integers or the
set of real numbers to the set of real numbers. We say
that f(x) is O(g(x)) if there are constants C and k such
that |f(x)| ≤ C|g(x)| whenever x > k.
This is read as “f(x) is big-O of g(x)” or
“g asymptotically dominates f.”
The constants C and k are called witnesses to the
relationship f(x) is O(g(x)).
If one pair of witnesses is found, then there are infinitely
many pairs.

© 2019 McGraw-Hill Education

 Illustration of Big-O Notation

© 2019 McGraw-Hill Education

 Questions 1

© 2019 McGraw-Hill Education

 Questions 2

Show that 7x2 is O(x3).

Solution: When x > 7, 7x2 < x3. Take C =1 and k = 7
as witnesses to establish that 7x2 is O(x3).
Note that 7x2 is also big-O of x2 and x2 grows much
slower than x3.
In fact, x2 would be the smallest possible power of
x suitable as the reference function in the big-O
estimate.

© 2019 McGraw-Hill Education

 Questions 3

Is it true that x3 is O(7x2)?

Proof: If C and k are witnesses, the inequality
x3 ≤ C(7x2) holds for all x > k.
Observe that the inequality x3 ≤ C(7x2) is equivalent
to the inequality x ≤ 7C, which follows by dividing
both sides by the positive quantity x2.
However, no matter what C is, it is not the case
that x ≤ 7C for all x > k no matter what k is,
because x can be made arbitrarily large.
Hence, x3 is not O(7x2).

© 2019 McGraw-Hill Education

 Big-O Estimates for Polynomials
Let f ( x)= an x n + an −1 x n −1 +  + a1 x + a0
where a0 , a1 , , an are real numbers with an ≠0.
Then f(x) is O(xn).
Proof: Using the triangle inequality, if x > 1 we have
| f ( x)=
| | an x n + an −1 x n −1 +  + a1 x1 + a0 |
≤ | an | x n + | an −1 | x n −1 +  + | a1 | x1 + | a0 |
(
= x n | an | + | an −1 | / x +  + | a1 | / x n −1 + | a0 | / x n )
≤ x n (| an | + | an −1 | +  + | a1 | + | a0 |)
Take C = | an | + | an−1 | +  + | a0 | and k = 1.
Then f(x) is O(xn).
© 2019 McGraw-Hill Education
 Big-O Estimates for some
Important Functions 1

Example 1: Use big-O notation to estimate the sum of

the first n positive integers.
Solution: 1 + 2 +  + n ≤ n + n +  n =n2
( )
1 + 2 +  + n is O n 2 taking
= C 1 and
= k 1.

Example 2: Use big-O notation to estimate the factorial

function f ( n) = n ! =1 × 2 ×  × n .
Solution: n ! =1 × 2 ×  × n ≤ n × n ×  × n =n n
( )
n ! is O n n taking
= C 1=
and k 1.

© 2019 McGraw-Hill Education

 Big-O Estimates for some
Important Functions 2

Example 3: Use big-O notation to estimate log n!

Solution: Given that n ! ≤ n n
then log ( n !) ≤ n ⋅ log ( n) .
Hence, log(n!) is O(n∙log(n)) taking C = 1 and k = 1.

© 2019 McGraw-Hill Education

 Big-O Estimates for some
Important Functions 3

Example 4: Show that n is O(2n), and log n is O(n).

Solution: Given that n < 2n (Use mathematical
induction to prove this inequality in Chapter 5)
With n < 2n, we quickly can conclude that n is O(2n)
by taking C = k = 1 as witnesses.
Taking logarithms (base 2) of both sides of n < 2n
shows that log n < n. It follows that log n is O(n),
by taking C = k = 1 as witnesses.

© 2019 McGraw-Hill Education

 Big-O Estimates for some
Important Functions 4

Example 5: Arrange the following functions

in a list so that each function is big-O of the next

function.
Solution: f2(n) is the slowest growing of these functions.
The next four functions, in order, are f1(n), f3(n), f6(n),
and f5(n). f4(n) is the fastest growing function on the list.

© 2019 McGraw-Hill Education

 Big-O Estimates for some
Important Functions 5

Example 6: Put the functions below in order so that

each function is big-O of the next function on the list.
f1 ( n) = (1.5)
n

f 2 ( n) =8n3 + 17 n 2 + 111
f 3 ( n) = ( log n )
2

f 4 ( n) = 2 n Solution: f 9(n), f5(n), f3(n), f6(n),

f 5 ( n) = log ( log n)
f8(n), f2(n), f1(n), f4(n), f7(n), f10(n).
f 6 ( n) = n 2 ( log n)
3

f=7 ( n) 2n ( n 2 + 1)
f8 ( n=) n3 + n ( log n) 2
f 9 ( n) = 10000
f10 ( n) = n !
© 2019 McGraw-Hill Education
 Combinations of Functions
If f1(x) is O(g1(x)) and f2(x) is O(g2(x)) then
( f1 + f2 )(x) is O(max(|g1(x) |,|g2(x) |)).
If f1(x) and f2(x) are both O(g(x)) then
( f1 + f2 )(x) is O(g(x)).
If f1(x) is O(g1(x)) and f2(x) is O(g2(x)) then
( f1f2)(x) = f1(x)f2(x) is O(g1(x)g2(x)).

See textbook for the proofs.

© 2019 McGraw-Hill Education

 Questions 1

Example 1: Give a big-O estimate for f(n) = 3n log(n!)

+ (n2+3) log n, where n is a positive integer.
Solution: We know that log(n!) is O(n log n).
Using this estimate and the fact that 3n is O(n),
the estimate of 3n log(n!) is O(n2 log n).
Next, consider the product (n2+3) log n
Because (n2+3) < 2n2 when n > 2, it follows that
(n2+3) is O(n2). Thus,(n2+3) log n is O(n2 log n).
The estimate for f(n) is O(n2 log n).

© 2019 McGraw-Hill Education

 Questions 2

Example 2: Give a big-O estimate for

f(x) = (x + 1) log(x2 + 1) + 3x2.
Solution: We know (x + 1) is O(x).
Furthermore, x2 + 1 ≤ 2x2 when x > 1.
Hence, log(x2 + 1) ≤ log(2x2) = log 2 + log x2
= log 2 + 2 log x ≤ 3 log x, if x > 2.
This shows that log(x2 + 1) is O(log x)
and (x + 1) log(x2 + 1) is O(x log x)
Because 3x2 is O(x2) and x log x ≤ x2 for x > 1,
it follows that f(x) is O(x2).

© 2019 McGraw-Hill Education

 Big-Omega Notation
Let f and g be functions from the set of integers or
the set of real numbers to the set of real numbers.
We say that f(x) is Ω(g(x)),
read as “f(x) is big-Omega of g(x)”,
if there are constants C and k such that
|f(x)| ≥ C|g(x)| when x > k.
Big-O gives an upper bound on the growth of a
function, while Big-Omega gives a lower bound.
Big-Omega tells us that a function grows at least
as fast as another.
f(x) is Ω(g(x)) if and only if g(x) is O(f(x)).
© 2019 McGraw-Hill Education
 Question
Example: Show that f ( x ) = 8 x 3
+ 5 x 2
+ 7 is
Ω ( g ( x) ) where g ( x) =
x3 .

Solution: f ( x) = 8 x3 + 5 x 2 + 7 ≥ 8 x3 for all

positive real numbers x.
This is equivalent to saying that
g(x) = x3 is O(8x3 + 5x2 + 7)

© 2019 McGraw-Hill Education

 Big-Theta Notation
Let f and g be functions from the set of integers or
the set of real numbers to the set of real numbers.
The function f(x) is Θ(g(x)),
read as “f(x) is big-Theta of g(x)”
if f(x) is O(g(x)) and f(x) is Ω(g(x)).
Note that f(x) is Θ(g(x))
if and only if there exists constants C1 , C2, and k
such that C1|g(x)| ≤ | f(x)| ≤ C2|g(x)|
whenever x > k. This follows from the
definitions of big-O and big-Omega.

© 2019 McGraw-Hill Education

 Questions 1

Example 1: Show that the sum of the first n positive

integers is Θ(n2).
Solution: Because we already know that f(n) is O(n2), to
show that f(n) is of order n2 we need to find a positive
constant C such that f(n) > Cn2 for sufficiently large
integers n. To obtain a lower bound for this sum, we can
ignore the first half of the terms.
Summing only the terms greater than ⌈n∕2⌉, we find that
1 + 2 + ⋯ + n ≥ ⌈n∕2⌉ + ( ⌈n∕2⌉ + 1) + ⋯ + n
≥ ⌈n∕2⌉ + ⌈n∕2⌉ + ⋯ + ⌈n∕2⌉ ≥ (n∕2)(n∕2) = n2∕4.
Taking C = ¼, f(n) > Cn2 for all positive integers n. Hence,
f(n) is Ω(n2), and we can conclude that f(n) is Θ(n2).
© 2019 McGraw-Hill Education
 Questions 2

Example 2: Show that 3x2 + 8x log x is Θ(x2).

Solution: Because 0 ≤ 8x log x ≤ 8x2, it follows that

3x2 ≤ 3x2 + 8x log x ≤ 11x2 for x > 1.
Consequently, 3x2 + 8x log x is Θ(x2).

Theorem: Let f(x) = anxn + an−1xn−1 + ⋯ + a1x + a0,

where a0, a1, … , an are real numbers with an ≠ 0.
Then f(x) is Θ(xn).

© 2019 McGraw-Hill Education

 Homework

Exercises: 1, 7, 13, 19, 21, 27, 35

© 2019 McGraw-Hill Education

 Section 3.3
Complexity of Algorithms

© 2019 McGraw-Hill Education

 The Complexity of Algorithms
Computational complexity: Given an algorithm, how
efficient is this algorithm for solving a problem given
input of a particular size? To answer this question,
we ask:
Time complexity: How much time does this
algorithm use to solve a problem?
Space complexity: How much computer memory
does this algorithm use to solve a problem?

© 2019 McGraw-Hill Education

 Time Complexity
To analyze the time complexity of algorithms,
we determine the number of operations, such as
comparisons and arithmetic operations (addition,
multiplication, etc.).
The worst-case time complexity provides an upper
bound on the number of operations an algorithm uses
to solve a problem with input of a particular size.
The average-case time complexity is the average
number of operations an algorithm uses to solve a
problem over all inputs of a particular size.

© 2019 McGraw-Hill Education

 Complexity Analysis of Algorithms
Determine the worst-case time complexity of the algorithm
for finding the maximum element in a finite sequence.
procedure max(a1, a2, …., an: integers)
max := a1
for i := 2 to n
if max < ai then max := ai
return max {max is the largest element}
Solution: Count the number of comparisons.
The max < ai comparison is made n − 1 times.
Each time i is incremented, a test is made to see if i ≤ n.
One last comparison determines that i > n.
Exactly 2(n − 1) + 1 = 2n − 1 comparisons are made.
Hence, the time complexity of the algorithm is Θ(n).
© 2019 McGraw-Hill Education
 Worst-Case Complexity of
Linear Search 1

Determine the worst-case time complexity of the

linear search algorithm in terms of the number of
comparisons used.
procedure linear search(x: integer,
a1, a2, …,an: distinct integers)
i := 1
while (i ≤ n and x ≠ ai)
i := i + 1
if i ≤ n then location := i
else location := 0
return location {location is the subscript of the term ai
that equals x, or is 0 if x is not found}
© 2019 McGraw-Hill Education
 Worst-Case Complexity of
Linear Search 2

Solution: Count the number of comparisons.

At each step two comparisons are made.
To end the loop, one comparison i ≤ n is made.
After the loop, one more i ≤ n comparison is made.
If x = ai , 2i + 1 comparisons are used.
If x is not on the list, 2n + 1 comparisons are made and
then an additional comparison is used to exit the loop.
So, in the worst case 2n + 2 comparisons are made.
Hence, the complexity is Θ(n).

© 2019 McGraw-Hill Education

 Average-Case Complexity of
Linear Search
Determine the average-case performance of the linear
search algorithm.
Solution: Assume the element is in the list and that the
possible positions are equally likely.
If x is the first term a1 of the list, three comparisons are needed,
one i ≤ n to determine whether the end of the list has been
reached, one x ≠ ai to compare x and the first term, and one i ≤ n
outside the loop. If x is the second term a2 of the list, two more
comparisons are needed, so that a total of five comparisons are
used. In general, if x = ai , the number of comparisons is 2i + 1.
Hence, the average number of comparisons used equals
which is Θ(n).

© 2019 McGraw-Hill Education

 Worst-Case Complexity of
Binary Search 1

Determine the time complexity of binary search in terms of

the number of comparisons used.
procedure binary search(x: integer, a1,a2,…, an: increasing integers)
i := 1 {i is the left endpoint of interval}
j := n {j is right endpoint of interval}
while (i < j)
m := ⌊(i + j)/2⌋
if x > am then i := m + 1
else j := m
if x = ai then location := i
else location := 0
return location {location is the subscript i of the term ai equal to
x, or 0 if x is not found}

© 2019 McGraw-Hill Education

 Worst-Case Complexity of
Binary Search 2

Solution: Assume (for simplicity) n = 2k elements. Note

that k = log n.
Two comparisons are made at each stage: i < j and x > am .
At the first iteration the size of the list is 2k and after the
first iteration it is 2k-1.
At the last step, a comparison tells us that the size of the
list is the size is 20 = 1 and the element is compared with
the single remaining element.
Hence, at most 2k + 2 = 2 log n + 2 comparisons are made.
Therefore, the time complexity is Θ (log n), better than
linear search.

© 2019 McGraw-Hill Education

 Worst-Case Complexity of
Bubble Sort
Determine the worst-case complexity of bubble sort in
terms of the number of comparisons made.
procedure bubble sort(a1,…,an: real numbers with n ≥ 2)
for i := 1 to n− 1
for j := 1 to n − i
if aj >aj+1 then interchange aj and aj+1
{a1,…, an is now in increasing order}

Solution: A sequence of n−1 passes is made through the

list. On each pass n − i comparisons are made. The total
number of comparisons is
(n − 1) + (n − 2) + ⋯ + 2 + 1 = n(n-1)/2, which is Θ(n2).
© 2019 McGraw-Hill Education
 Worst-Case Complexity of
Insertion Sort
Determine the worst-case complexity of insertion sort
in terms of the number of comparisons made.
procedure insertion sort(a1,…,an: Solution: In the worst
real numbers with n ≥ 2) case, j comparisons are
for j := 2 to n required to insert the jth
i := 1 element into the correct
while aj > ai position The total
i := i + 1
number of comparisons
m := aj
for k := 0 to j − i − 1
is 2 + 3 + ⋯ + n =
𝑛𝑛(𝑛𝑛+1)
aj-k := aj-k-1 -1,
2
ai := m
{Now a1,…,an is in increasing order} which is Θ(n2)

© 2019 McGraw-Hill Education

 Matrix Multiplication Algorithm
Suppose that C = [cij] is the m × n matrix that is the
product of the m × k matrix A = [aij] and the k × n
matrix B = [bij].
procedure matrix multiplication(A,B: matrices)
for i := 1 to m
for j := 1 to n
cij := 0
for q := 1 to k
cij := cij + aiq bqj
return C {C = [cij] is the product of A and B}

© 2019 McGraw-Hill Education

 Complexity of Matrix Multiplication
How many additions of integers and multiplications of
integers are used by the matrix multiplication algorithm
to multiply two n × n matrices?
Solution: There are n2 entries in the product. Finding
each entry requires n multiplications and n − 1
additions. Hence, n3 multiplications and n2(n − 1)
additions are used.
Hence, the complexity of matrix multiplication is O(n3).

© 2019 McGraw-Hill Education

 Boolean Product Algorithm
The definition of Boolean product of zero-one matrices
can also be converted to an algorithm.

procedure Boolean product(A,B: zero-one matrices)

for i := 1 to m
for j := 1 to n
cij := 0
for q := 1 to k
cij := cij ∨ (aiq ∧ bqj)
return C {C = [cij] is the Boolean product of A and B}

© 2019 McGraw-Hill Education

 Complexity of Boolean Product
How many bit operations are used to find A ⊙ B,
where A and B are n × n zero-one matrices?
Solution: There are n2 entries in the A ⊙ B. A total of
n ORs and n ANDs are used to find each entry.
Hence, each entry takes 2n bit operations. A total of
2n3 operations are used.
Therefore, the complexity is O(n3)

© 2019 McGraw-Hill Education

 Matrix-Chain Multiplication
In which order should the integer matrices A1, A2, and A3,
where A1 is 30 × 20, A2 is 20 × 40, A3 is 40 × 10, be
multiplied to use the least number of multiplications.
Solution: There are two possible ways to compute A1A2A3.
A1(A2A3): A2A3 takes 20 ∙ 40 ∙ 10 = 8000 multiplications.
Then, to multiply A1 and A2A3 takes 30 ∙ 20 ∙ 10 = 6000
multiplications.
So the total number is 8000 + 6000 = 14,000.
(A1A2)A3: A1A2 takes 30 ∙ 20 ∙ 40 = 24,000 multiplications.
Then, to multiply A1A2 and A3 takes 30 ∙ 40 ∙ 10 = 12,000
multiplications.
So the total number is 24,000 + 12,000 = 36,000.
© 2019 McGraw-Hill Education
 Understanding the Complexity of
Algorithms 1

Complexity Terminology
Θ(1) Constant complexity
Θ(log n) Logarithmic complexity
Θ(n) Linear complexity
Θ(n log n) Linearithmic complexity
Θ(nb) Polynomial complexity
Θ(bn), where b > 1 Exponential complexity
Θ(n!) Factorial complexity

© 2019 McGraw-Hill Education

 Understanding the Complexity of
Algorithms 2

Assume that each bit operation takes 10−11 seconds.

Times of more than 10100 years are indicated with an *.
© 2019 McGraw-Hill Education
 Complexity of Problems
Class P (Tractable Problem): There exists a polynomial time
algorithm to solve this problem.
Class NP (Nondeterministic Polynomial time) : Solution can be
checked in polynomial time. But no polynomial time algorithm
has been found for finding a solution to problems in this class.
The satisfiability problem is an example of an NP problem.
NP Complete: If you find a polynomial worst-case time
algorithm for one member of the class, it can be used to solve
all the problems in the class. The satisfiability problem is also
an example of an NP-complete problem.
P versus NP problem asks whether P = NP???
P ≠ NP means that no NP-complete problem can be solved in
polynomial time.
© 2019 McGraw-Hill Education
 Homework

Exercises: 3, 9, 13, 33, 49

© 2019 McGraw-Hill Education