MODULE 2

Department of CSE, Dayananda Sagar University, Harohalli,

Karnataka
 Brute Force
A straightforward approach, usually based directly on the problem’s statement and definitions of the
concepts involved.

“ A straight forward technique to find the solution for the given problem “

Examples:

1. Computing 𝑎𝑛 (a > 0, n nonnegative integer)

2. Computing n!

3. Multiplying two matrices

4. Searching for a key of a given value in a list

Department of CSE, Dayananda Sagar University, Harohalli, Karnataka

 Brute-Force Sorting Algorithm
Selection Sort :

Scan the array to find its smallest element and swap it with
the first element.
Then, starting with the second element, scan the elements to
the right of it to find the smallest among them and swap it
with the second elements.
Generally, on pass i (0 <=i <=n-2), find the smallest element in
A[i..n-1] and swap it with A[i]:
A[0] <= . . . <=A[i-1] | A[i], . . . , A[min], . . ., A[n-1]
in their final positions.

Example: 7 5 4 2

Department of CSE, Dayananda Sagar University, Harohalli, Karnataka

Analysis of Selection Sort

Time efficiency: Θ(𝑛2 )

Space efficiency: Θ(1) , so in place

Stability: YES

Department of CSE, Dayananda Sagar University, Harohalli, Karnataka

 Brute-Force String Matching
❑ Pattern: a string of m characters to search for
❑ Text: a (longer) string of n characters to search in
❑ Problem: find a substring in the text that matches the pattern

Brute-force algorithm:
Step 1: Align pattern at beginning of text

Step 2 : Moving from left to right, compare each character of pattern to the corresponding character in text until–
all characters are found to match (successful search); or–a mismatch is detected

Step 3: While pattern is not found and the text is not yet exhausted, realign pattern one position to the right and
repeat Step 2

Department of CSE, Dayananda Sagar University, Harohalli, Karnataka

Examples of Brute-Force String Matching

1. Pattern: 001011 2. Pattern: happy

Text: 10010101101001100101111010 Text: It is never too late to have a happy childhood.

Department of CSE, Dayananda Sagar University, Harohalli, Karnataka

Pseudocode and Efficiency

Worst case time complexity: m(n-m+1)

i.e. O(nm)

Department of CSE, Dayananda Sagar University, Harohalli,

Karnataka
Brute-Force Strengths and Weaknesses
❑Strengths ::
➢Wide applicability
➢Simplicity
➢Yields reasonable algorithms for some important problems
(e.g., matrix multiplication, sorting, searching, string matching)

❑ Weaknesses ::
➢Rarely yields efficient algorithms
➢Some brute-force algorithms are unacceptably slow
➢ Not as constructive as some other design techniques

Department of CSE, Dayananda Sagar University, Harohalli,

Karnataka
 Traveling Salesman Problem
❑ Given N cities with known distances between each pair, find
the shortest tour that passes through all the cities exactly
once before returning to the starting city
❑ Alternatively: Find shortest Hamiltonian circuit in a weighted
connected graph
❑ Example:
TSP by Exhaustive Search::
Tour Cost
a→ b→ c→ d→ a = 2+3+7+5 = 17
a→ b→ d→ c→ a = 2+4+7+8 = 21
a→ c→ b→ d→ a = 8+3+4+5 = 20
a→ c→ d→ b→ a = 8+7+4+2 = 21
a→ d→ b→ c→ a = 5+4+3+8 = 20
a→ d→ c→ b→ a = 5+7+3+2 = 17

Efficiency: Θ((n-1)!)
Department of CSE, Dayananda Sagar University, Harohalli, Karnataka
Analysis of Algorithms

Recurrences
(Chapter 2)

Department of CSE, Dayananda Sagar University, Harohalli,

Karnataka
 Recurrences and Running Time
• An equation or inequality that describes a function in terms of
its value on smaller inputs.
T(n) = T(n-1) + n
• Recurrences arise when an algorithm contains recursive calls to
itself

• What is the actual running time of the algorithm?

• Need to solve the recurrence

• Find an explicit formula of the expression
• Bound the recurrence by an expression that involves n
Department of CSE, Dayananda Sagar University, Harohalli,
Karnataka
 Example Recurrences

• T(n) = T(n-1) + n Θ(n2)

• Recursive algorithm that loops through the input to eliminate one item
• T(n) = T(n/2) + c Θ(lgn)
• Recursive algorithm that halves the input in one step
• T(n) = T(n/2) + n Θ(nlgn)
• Recursive algorithm that halves the input but must examine every item in the
input
• T(n) = 2T(n/2) + 1 Θ(n)
• Recursive algorithm that splits the input into 2 halves and does a constant
amount of other work
Department of CSE, Dayananda Sagar University, Harohalli,
Karnataka
Recurrent Algorithms
BINARY-SEARCH
• for an ordered array A, finds if x is in the array A[lo…hi]

Alg.: BINARY-SEARCH (A, lo, hi, x)

1 2 3 4 5 6 7 8

if (lo > hi) 2 3 5 7 9 10 11 12

return FALSE
mid  (lo+hi)/2 mid
lo hi
if x = A[mid]
return TRUE
if ( x < A[mid] )
BINARY-SEARCH (A, lo, mid-1, x)
if ( x > A[mid] )
BINARY-SEARCH (A, mid+1, hi, x)
Example
• A[8] = {1, 2, 3, 4, 5, 7, 9, 11}
• lo = 1 hi = 8 x = 7
1 2 3 4 5 6 7 8

1 2 3 4 5 7 9 11 mid = 4, lo = 5, hi = 8

5 6 7 8

1 2 3 4 5 7 9 11 mid = 6, A[mid] = x Found!

Another Example
• A[8] = {1, 2, 3, 4, 5, 7, 9, 11}
– lo = 1 hi = 8 x=6
1 2 3 4 5 6 7 8

1 2 3 4 5 7 9 11 mid = 4, lo = 5, hi = 8
low high

1 2 3 4 5 7 9 11 mid = 6, A[6] = 7, lo = 5, hi = 5
low high

1 2 3 4 5 7 9 11 mid = 5, A[5] = 5, lo = 6, hi = 5
NOT FOUND!

1 2 3 4 5 7 9 11
high low
 Analysis of BINARY-SEARCH
Alg.: BINARY-SEARCH (A, lo, hi, x)
if (lo > hi)
constant time: c1
return FALSE
mid  (lo+hi)/2 constant time: c2
if x = A[mid]
constant time: c3
return TRUE
if ( x < A[mid] )
BINARY-SEARCH (A, lo, mid-1, x) same problem of size n/2
if ( x > A[mid] )
BINARY-SEARCH (A, mid+1, hi, x) same problem of size n/2

• T(n) = c + T(n/2)
• T(n) – running time for an array of size n
Department of CSE, Dayananda Sagar University, Harohalli,
Karnataka
 Methods for Solving
Recurrences

•Iteration method

•Substitution method

•Recursion tree method

•Master method
Department of CSE, Dayananda Sagar University, Harohalli,
Karnataka
The Iteration Method
• Convert the recurrence into a summation and try to bound it using
known series
• Iterate the recurrence until the initial condition is reached.
• Use back-substitution to express the recurrence in terms of n and the initial
(boundary) condition.

Department of CSE, Dayananda Sagar University, Harohalli,

Karnataka
 The Iteration Method

T(n) = c + T(n/2)
T(n/2) = c + T(n/4)
T(n) = c + T(n/2)
T(n/4) = c + T(n/8)
= c + c + T(n/4)
= c + c + c + T(n/8)
Assume n = 2k
T(n) = c + c + … + c + T(1)
k times
= clgn + T(1)
= Θ(lgn)

Department of CSE, Dayananda Sagar University, Harohalli,

Karnataka
 Iteration Method – Example
T(n) = n + 2T(n/2) Assume: n = 2k
T(n) = n + 2T(n/2) T(n/2) = n/2 + 2T(n/4)
= n + 2(n/2 + 2T(n/4))
= n + n + 4T(n/4)
= n + n + 4(n/4 + 2T(n/8))
= n + n + n + 8T(n/8)
… = in + 2iT(n/2i)
= kn + 2kT(1)
= nlgn + nT(1) = Θ(nlgn)
Department of CSE, Dayananda Sagar University, Harohalli,
Karnataka
The substitution method

1. Guess a solution

2. Use induction to prove that the

solution works

Department of CSE, Dayananda Sagar University, Harohalli,

Karnataka
Substitution method
• Guess a solution
• T(n) = O(g(n))

• Induction goal: apply the definition of the asymptotic notation

• T(n) ≤ d g(n), for some d > 0 and n ≥ n0 (strong induction)

• Induction hypothesis: T(k) ≤ d g(k) for all k < n

• Prove the induction goal

• Use the induction hypothesis to find some values of the constants d and n0 for which the
induction goal holds
Department of CSE, Dayananda Sagar University, Harohalli,
Karnataka
 Example: Binary Search
T(n) = c + T(n/2)
• Guess: T(n) = O(lgn)
• Induction goal: T(n) ≤ d lgn, for some d and n ≥ n0
• Induction hypothesis: T(n/2) ≤ d lg(n/2)

• Proof of induction goal:

T(n) = T(n/2) + c ≤ d lg(n/2) + c
= d lgn – d + c ≤ d lgn
if: – d + c ≤ 0, d ≥ c
• Base case? Department of CSE, Dayananda Sagar University, Harohalli,
Karnataka
 Example 2

T(n) = T(n-1) + n
• Guess: T(n) = O(n2)
• Induction goal: T(n) ≤ c n2, for some c and n ≥ n0
• Induction hypothesis: T(n-1) ≤ c(n-1)2 for all k < n

• Proof of induction goal:

T(n) = T(n-1) + n ≤ c (n-1)2 + n
= cn2 – (2cn – c - n) ≤ cn2
if: 2cn – c – n ≥ 0  c ≥ n/(2n-1)  c ≥ 1/(2 – 1/n)
• For n ≥ 1  2 – 1/n ≥ 1  any c ≥ 1 will work
Department of CSE, Dayananda Sagar University, Harohalli,
Karnataka
 Example 3
T(n) = 2T(n/2) + n
• Guess: T(n) = O(nlgn)
• Induction goal: T(n) ≤ cn lgn, for some c and n ≥ n0
• Induction hypothesis: T(n/2) ≤ cn/2 lg(n/2)

• Proof of induction goal:

T(n) = 2T(n/2) + n ≤ 2c (n/2)lg(n/2) + n
= cn lgn – cn + n ≤ cn lgn
if: - cn + n ≤ 0  c ≥ 1
• Base case? Department of CSE, Dayananda Sagar University, Harohalli,
Karnataka
Changing variables
T(n) = 2T( n ) + lgn
• Rename: m = lgn  n = 2m
T (2m) = 2T(2m/2) + m
• Rename: S(m) = T(2m)
S(m) = 2S(m/2) + m  S(m) = O(mlgm)
(demonstrated before)
T(n) = T(2m) = S(m) = O(mlgm)=O(lgnlglgn)
Idea: transform the recurrence to one that you have
seen before
The recursion-tree method

Convert the recurrence into a tree:

• Each node represents the cost incurred at various levels
of recursion

• Sum up the costs of all levels

Used to “guess” a solution for the recurrence

 Example 1
W(n) = 2W(n/2) + n 2

• Subproblem size at level i is: n/2i

• Subproblem size hits 1 when 1 = n/2i  i = lgn
• Cost of the problem at level i = (n/2i)2 No. of nodes at level i = 2i
• Total cost: lg n−1 2 lg n −1 i  i
n 1 1 1
W ( n) = 2
i =0
i
+ 2 lg n
W (1) = n 2
  
i =0  2 
+ n  n 2
  
i =0  2 
+ O ( n ) =n 2

1− 1
+ O ( n) = 2n 2

 W(n) = O(n ) 2 2
Department of CSE, Dayananda Sagar University, Harohalli,
Karnataka
Example 2
E.g.: T(n) = 3T(n/4) + cn2

• Subproblem size at level i is: n/4i

• Subproblem size hits 1 when 1 = n/4i  i = log4n
• Cost of a node at level i = c(n/4i)2
• Number of nodes at level i = 3i  last level has 3log4n = nlog43 nodes
• Total cost:
log 4 n −1 i

( ) ( ) ( )
 i
3 2 3 1
T ( n) =    cn +  n
 16 
log 4 3
    cn2 +  n log 4 3 =
i = 0  16 
3
cn2 +  n log 4 3 = O(n 2 )
i =0
1−
16
 T(n) = O(n ) 2
 Example 2 - Substitution
T(n) = 3T(n/4) + cn2
•Guess: T(n) = O(n2)
• Induction goal: T(n) ≤ dn2, for some d and n ≥ n0
• Induction hypothesis: T(n/4) ≤ d (n/4)2

•Proof of induction goal:

T(n) = 3T(n/4) + cn2
≤ 3d (n/4)2 + cn2
= (3/16) d n2 + cn2
≤ d n2 if: d ≥ (16/13)c

•Therefore: T(n) = O(n2)

Department of CSE, Dayananda Sagar University, Harohalli,

Karnataka
Example 3 (simpler proof)
W(n) = W(n/3) + W(2n/3) + n

• The longest path from the root to

a leaf is:
n → (2/3)n → (2/3)2 n → … → 1

• Subproblem size hits 1 when

1 = (2/3)in  i=log3/2n

• Cost of the problem at level i = n

• Total cost:
lg n
W (n)  n + n + ... = n(log 3/ 2 n) = n = O (n lg n)
3
lg
2
 W(n) = O(nlgn)
Example 3
W(n) = W(n/3) + W(2n/3) + n

• The longest path from the root to

a leaf is:
n → (2/3)n → (2/3)2 n → … → 1

• Subproblem size hits 1 when

1 = (2/3)in  i=log3/2n

• Cost of the problem at level i = n

• Total cost:
(log3 / 2 n ) −1
W (n)  n + n + ... = i =0
n + 2(log3 / 2 n )W (1) 
log3 / 2 n
lg n 1
n 
i =0
1 + nlog3 / 2 2 = n log3/ 2 n + O(n) = n
lg 3/ 2
+ O ( n) =
lg 3/ 2
n lg n + O(n)

 W(n) = O(nlgn)
 Example 3 - Substitution
W(n) = W(n/3) + W(2n/3) + O(n)
• Guess: W(n) = O(nlgn)
• Induction goal: W(n) ≤ dnlgn, for some d and n ≥ n0
• Induction hypothesis: W(k) ≤ d klgk for any K < n
(n/3, 2n/3)
• Proof of induction goal:
Try it out as an exercise!!
• T(n) = O(nlgn)

Department of CSE, Dayananda Sagar University, Harohalli,

Karnataka
Master’s method
•“Cookbook” for solving recurrences of the form:
n
T (n) = aT   + f (n)
b
where, a ≥ 1, b > 1, and f(n) > 0

Idea: compare f(n) with nlogba

•f(n) is asymptotically smaller or larger than nlogba by a
polynomial factor n

•f(n) is asymptotically equal with nlogba

Master’s method
•“Cookbook” for solving recurrences of the form:
n
T (n) = aT   + f (n)
b

where, a ≥ 1, b > 1, and f(n) > 0

Case 1: if f(n) = O(nlogba -) for some  > 0, then: T(n) = (nlogba)

Case 2: if f(n) = (nlogba), then: T(n) = (nlogba lgn)

Case 3: if f(n) = (nlogba +) for some  > 0, and if

af(n/b) ≤ cf(n) for some c < 1 and all sufficiently large n, then:

regularity condition T(n) = (f(n))

Examples

T(n) = 2T(n/2) + n

a = 2, b = 2, log22 = 1

Compare nlog22 with f(n) = n

 f(n) = (n)  Case 2

 T(n) = (nlgn)
Examples
T(n) = 2T(n/2) + n2
a = 2, b = 2, log22 = 1
Compare n with f(n) = n2
 f(n) = (n1+) Case 3  verify regularity cond.
a f(n/b) ≤ c f(n)
 2 n2/4 ≤ c n2  c = ½ is a solution (c<1)
 T(n) = (n2)
Examples (cont.)

T(n) = 2T(n/2) + n

a = 2, b = 2, log22 = 1

Compare n with f(n) = n1/2

 f(n) = O(n1-) Case 1

 T(n) = (n)
Examples
T(n) = 3T(n/4) + nlgn

a = 3, b = 4, log43 = 0.793

Compare n0.793 with f(n) = nlgn

f(n) = (nlog43+) Case 3

Check regularity condition:

3(n/4)lg(n/4) ≤ (3/4)nlgn = c f(n), c=3/4

T(n) = (nlgn)
Department of CSE, Dayananda Sagar University, Harohalli,
Karnataka
Examples
T(n) = 2T(n/2) + nlgn

a = 2, b = 2, log22 = 1

• Compare n with f(n) = nlgn

• seems like case 3 should apply

• f(n) must be polynomially larger by a factor of n

• In this case it is only larger by a factor of lgn

Department of CSE, Dayananda Sagar University, Harohalli,

Karnataka
Department of CSE, Dayananda Sagar University, Harohalli,
Karnataka