Discrete Structures
Fundamentals of Alg. : Complexity
(Ch 3.3)*
CMPS 211 – American University of Beirut
* Extracted from Discrete Mathematics and It’s Applications book
slides
1
Complexity of Algorithms
2
The Complexity of Algorithms
Given an algorithm, how efficient is this
algorithm for solving a problem given
input of a particular size?
To answer this question, we ask
How much time does this algorithm use to solve
a problem?
How much space (computer memory) does this
algorithm use to solve a problem?
3
The Complexity of Algorithms
When we analyze the time the algorithm uses to
solve the problem given input of a particular size,
we are studying the time complexity of the algorithm
When we analyze the computer memory the
algorithm uses to solve the problem given input of a
particular size, we are studying the space
complexity of the algorithm
In most problems, there is a time-space tradeoff between
different solutions(algorithms) for the problem
We often deal with estimates!
4
Space Complexity
5
Space Complexity
To compute the how much space is required
for an algorithms to run, we have to study two
types of algorithm data items:
1. Fixed part: The number of fixed data items that are
independent of the size of the problem:
Accumulator, control variables in loops, etc…
2. Variable part: The number of data items that are directly
dependent on the input size and change with it:
Array of items, set, auxiliary/temporary arrays
Sp(n) = c + f(n)
c is a constant, and f(n) is the function for the variable part
6
Time Complexity
7
Time Complexity
To analyze the time complexity of algorithms, we determine
the number of operations, such as
comparisons,
arithmetic operations (addition, multiplication, etc.),
accessing variable value,
assigning value to variable, etc…
We can estimate the time a computer may actually use to
solve a problem using the amount of time required to do
basic operations
We ignore minor details, such as the “house keeping”
aspects of the algorithm
We will also notice that a constant order of increase in the
number of operations will not affect the total runtime!
8
Time Complexity
Three types of time complexities:
The worst-case time complexity of an algorithm provides
an upper bound on the number of operations an algorithm
uses to solve a problem with input of a particular size
Basically, it’s the scenario (input) for which the algorithms uses
the most number of operations to terminate
The best-case time complexity provides a lower bound on
the number of operations required
Basically, it’s the scenario (input) for which the algorithms uses
the least number of operations to terminate
The average case time complexity of an algorithm
This is the average number of operations an algorithm uses to
solve a problem over all inputs of a particular size
9
The Complexity of Algorithms
In this course, we will “mainly” focus on time complexity
We will measure time complexity in terms of the number of
comparisons an algorithm uses, and we will use big-O and
big-Theta notation to estimate the time complexity
Note that changing hardware will affect the time complexity in a
constant factor, and doesn’t affect the growth rate T(n)
The runtime complexity T(n) is an intrinsic property of the
algorithm
We can use this analysis to see whether it is practical to use
this algorithm to solve problems with input of a particular
size
We can also compare the efficiency of different algorithms
for solving the same problem
10
Time Complexity
Often more important than space complexity
space (memory) available tends to be larger and larger
time is still a problem for all of us
The CPUs in the commercial market nowadays
operate on 3-4 GHz
This is 3-4 Million cycles per second
However, the computation of the various transformations
for 1 single DNA chain on 1 TerraHz computers are
estimated to take 1 year to terminate
Therefore, it is essential to estimate the runtime
complexity of algorithms before (implementing
and) running them
11
Running time - Motivation
Suppose an arbitrary program that includes:
if-then statements that may execute or not
and while loops that might execute variable number of
times:
This program will have variable running time on various
inputs
We often care about worst-case complexity
Easier to compute
Crucial for some applications
12
Sample Algorithms
13
Complexity Analysis of Max Alg.
Describe the time & space complexities of the algorithm for
finding the maximum element in a finite sequence of integers
procedure max(a1, a2, …., an: integers)
1. max := a1
2. for i := 2 to n
3. if max < ai then max := ai
4. return max {max is the largest element}
Solution: For time complexity, count the number of operations
line 1 will be executed 1 time, and costs 1 operation 1 op
line 2 will be executed n-1 times, and an additional one last time where the
condition gets evaluated to false, and each execution costs 2 operations
(increment & condition) 2n ops
line 3 will be executed n-1 times, and execution costs 2 operations at max
2(n-1) ops
line 4 is just a return statement 1 op
Therefore, the total number of operations is T(n) = 1 + 2n + 2(n-1) + 1 =
4n
14
Complexity Analysis of Max Alg.
Describe the time & space complexities of the algorithm
for finding the maximum element in a finite sequence of
integers procedure max(a1, a2, …., an: integers)
1. max := a1
2. for i := 2 to n
3. if max < ai then max := ai
4. return max {max is the largest element}
Solution: For space complexity, count the number of
data items used
Input parameter is array of n elements n data items
The fixed part of space is for creating the data items max, and
the loop control variable i 2 data items
15
Therefore the total number of data items S(n) = n + 2
Complexity Analysis of Max Alg.
Describe the time & space complexities of the algorithm for finding
the maximum element in a finite sequence of integers
procedure max(a1, a2, …., an: integers)
1. max := a1
2. for i := 2 to n
3. if max < ai then max := ai
4. return max {max is the largest element}
We have T(n) = 4n, and S(n) = n + 2
Accordingly the growth rates of those functions would be:
T(n) = 4n T(n) is O(n)
S(n) = n+2 S(n) is O(n)
This is the worst-case time complexity, What is the best-case time
complexity?
In best case, the max is the first element, and therefore the if condition is
always false we save n-1 operations T(n) = 3n – 1, which is O(n)
Therefore, T(n) is Θ(n)
We can also conclude that the average-case time complexity is also O(n)
16
Complexity of Linear Search
Determine the complexity of the linear search algorithm
procedure linear search(x:integer, a1, a2, …,an: distinct
integers)
1. i := 1
2. while (i ≤ n and x ≠ ai)
3. i=i +1
4. if i ≤ n then
5. location := i
6. else location := 0
7. return location
Solution: Count the number of comparisons - worst case scenario
when x is not found in the array
line 2 executes n+1 times at max, and costs 2 comparisons each time
2(n+1) comparisons
line 4 executes once, and costs 1 comparison
Therefore, the worst case complexity is T(n) = 2(n+1) + 1 = 2n + 3 which
is O(n)
17
Complexity of Linear Search
Determine the complexity of the linear search
algorithm
procedure linear search(x:integer, a , a , …,a : distinct
1 2 n
integers)
1. i := 1
2. while (i ≤ n and x ≠ ai)
3. i=i +1
4. if i ≤ n then
5. location := i
6. else location := 0
7. return location
Solution: In best-case scenario, x is found at the first index of the
array
line 2 executes 1 time 2 comparisons
line 4 executes once 1 comparison
Therefore, the best-case complexity is T(n) = 1 + 2 = 3 which is O(1)
18
Complexity of Linear Search
Determine the complexity of the linear search algorithm
procedure linear search(x:integer, a1, a2, …,an: distinct
integers)
1. i := 1
2. while (i ≤ n and x ≠ ai)
3. i=i +1
4. if i ≤ n then
5. location := i
6. else location := 0
7. return location
Solution: In average-case scenario, x is equally likely to be
anywhere in the array
The loop iterates depending on the position of x in A
If x was found at position i, then the condition will be checked i
times, and a total of 2i comparisons will be needed if x was found
at position I
One more comparison at line 4 so T(i) = 2i + 1
19
Complexity of Linear Search
Determine the complexity of the linear search algorithm
procedure linear search(x:integer, a1, a2, …,an: distinct Linear Search:
integers)
1. i := 1
• T(n) is O(n)
2. while (i ≤ n and x ≠ ai)
• T(n) is Ω(1)
3. i=i +1
4. if i ≤ n then
5. location := i
6. else location := 0
7. return location
T(i) = 2i+1 and we have n+1 cases (n positions, and when its not in the array)
So the average-case complexity is O(n)
20
Complexity of Binary Search
Describe the complexity of binary
procedure binary search(x: integer, a1,a2,…, an: increasing integers)
1. i := 1 {i is the left endpoint of interval}
2. j := n {j is right endpoint of interval}
3. while i < j
4. m := ⌊(i + j)/2⌋
5. if x > am then i := m + 1
6. else j := m
7. if x = ai then location := i
8. else location := 0
9. return location {location is the subscript i of the term ai equal to x, or 0 if x is not found}
Solution: Assume (for simplicity) n = 2k elements k = log n
Two comparisons are made at each stage: i < j, and x > a
m
At the first iteration the size of the list is 2k and after the first iteration it is 2k-1,
then 2k-2 and so on until the size of the list is 21 = 2
At the last step, a comparison tells us that the size of the list is 20 = 1 and the
element is compared with the single remaining element so two more comparisons
Hence, at most 2k + 2 = 2 lg n + 2 comparisons are made so T(n) is O(lgn)
Note that there isn’t a best and worst case scenarios in (this) binary search
algorithm, since no matter where the element x is, we have to do all the steps, and
the while loop will always iterate k+1 times, and therefore T(n) = Θ(lgn)
21
Complexity of Bubble Sort
What is the complexity of bubble sort?
procedure bubblesort(a1,…,an: real numbers )
1. for i := 1 to n− 1
2. for j := 1 to n − i
3. 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
T(n) = (n – 1) + (n - 2) + … + 2 + 1 = n(n-1)/2
which is O(n2)
Best case is also O(n2)
Thus, we can conclude that T(n) is Θ(n 2)
22
Complexity of Insertion Sort
What is the complexity
procedure insertion_sort (a1, a2,
of insertion sort?
…, a )
1. for j := 2 to n
n
2. temp := aj
Solution: In the worst
case, the list is sorted 3. i := j-1
4. while i > 0 and ai >
in reverse order temp
The number of 5. ai+1 := ai
6. i := i -1
comparisons in the
worst-case are: 7. ai := temp
1 + 2 + 3 + …. + (n-1) = {a1, a2, …, an are sorted }
n(n-1)/2 = O(n2)
23
Complexity of Insertion Sort
What is the
procedure insertion_sort (a1, a2,
complexity of
…, an)
insertion sort? 1. for j := 2 to n
2. temp := aj
Solution: In the best 3. i := j-1
4. while i > 0 and ai >
case, the list is
temp
already sorted 5. ai+1 := ai
6. i := i -1
The number of
comparisons in the 7. ai := temp
best case are 1
Therefore, Insertion Sort
{a1, a2, …, Bubble
outperforms an are sorted }
sort on sorted
comparison n-1 times: input. However, Bubble sort is easier
n -1 = O(n) to implement
24
Algorithmic Paradigms
25
Algorithmic Paradigms
An algorithmic paradigm is a general approach
based on a particular concept for constructing
algorithms to solve a variety of problems
Greedy algorithms were introduced in Section 3.1
We will discuss brute-force algorithms in this section
We will see divide-and-conquer algorithms (Chapter
8)
There is also dynamic programming (Chapter 8),
backtracking (Chapter 11), and probabilistic
algorithms (Chapter 7)
There are many other paradigms that you may see in
later courses
26
Brute-Force Algorithms
A brute-force algorithm is solved in the most
straightforward manner, without taking
advantage of any ideas that can make the
algorithm more efficient
Brute-force algorithms we have previously
seen are linear search, bubble sort, and
insertion sort
27
Computing the Closest Pair of Points
Construct a brute-force algorithm for finding
the closest pair of points in a set of n points
in the plane and provide a worst-case
estimate of the number of arithmetic
operations
Solution: Recall that the distance between
(xi,yi) and (xj, yj) is
A brute-force algorithm simply computes the
distance between all pairs of points and picks
the pair with the smallest distance
Note: There is no need to compute the square root, since the
square of the distance between two points is smallest when the
distance is smallest
28 Continued →
Closest Pair of Points by Brute-Force
Algorithm for finding the closest pair in a set of n points
procedure closest pair((x1, y1), (x2, y2), … ,(xn, yn): xi, yi real numbers)
min = ∞
for i := 1 to n-1
for j := i+1 to n
if (xj − xi)2 + (yj − yi)2 < min
then min := (xj − xi)2 + (yj − yi)2
closest pair := (xi, yi), (xj, yj)
return closest pair
The algorithm loops through n(n −1)/2 pairs of points,
computes the value (xj − xi)2 + (yj − yi)2 and compares it
with the minimum, etc.
So, the algorithm uses Θ(n2) arithmetic and comparison
operations
29
Understanding the Complexity of
Algorithms
30
Understanding the Complexity of
Algorithms
Assume each operation takes 10-11 s
Times of more than 10100 years are indicated with
an *
31
Complexity of Problems
Tractable Problem:
There exists a polynomial time algorithm to solve this problem
These problems are said to belong to the Class P
Intractable Problem:
There does not exist a polynomial time algorithm to solve this
problem
Unsolvable Problem:
No algorithm exists to solve this problem, e.g., halting problem
Class NP:
Solution can be checked in polynomial time
But no polynomial time algorithm has been found for finding a
solution to problems in this class
NP Complete Class:
If you find a polynomial time algorithm for one member of the
class, it can be used to solve all the problems in the class
More about all this in CMPS 257!
32
Stephen
Cook
P Versus NP Problem (Born 1939)
The P versus NP problem asks whether the class P = NP? Are there
problems whose solutions can be checked in polynomial time, but
cannot be solved in polynomial time? if so, then P ≠ NP
Note that just because “no one has found a polynomial time algorithm” is
different from showing that the problem cannot be solved by a polynomial
time algorithm
If a polynomial time algorithm for any of the problems in the NP
complete class were found, then that algorithm could be used to obtain
a polynomial time algorithm for every problem in the NP complete
class
Satisfiability (in Section 1.3) is an NP complete problem
It is generally believed that P≠NP since no one has been able to find a
polynomial time algorithm for any of the problems in the NP complete
class
The problem of P versus NP remains one of the most famous unsolved
problems in mathematics (including theoretical computer science)
The Clay Mathematics Institute has offered a prize of $1,000,000 for a
solution
33
Any Questions?
34
