(Chapter 2)
1. Efficiency of an algorithm depends on input size
2. Efficiency of an algorithm also depends on basic operation
3. Efficiency can be expressed by counting the basic operation
1. Loops(A[0..n-1])
2. for i 1 to n-1 do
3. v A[i]
4. j i-1
5. while j0 and A[j]>v do
6. A[j+1] A[j] n 1 i 1
n(n 1) n 2 n n 2
7. j j-1 C (n) 1
8. A[j+1] v i 1 j 0 2 2 2 2
Problem: find the max element in a list
Input size measure:
◦ Number of list’s items, i.e. n
Basic operation:
◦ Comparison
n 1
C ( n) 1 n 1
i 1
Problem: Multiplication of two matrices
Input size measure:
◦ Matrix dimensions or total number of elements
Basic operation:
◦ Multiplication of two numbers
n 1 n 1 n 1
C (n) 1 = 𝑛3
i 0 j 0 k 0
Problem: calculating sum
Input size measure:
◦ Number n
Basic operation:
◦ Addition
1. Example3(n)
2. sum 0
3. i n
4. while i 1
4. sum sum +1
5. i i/2
6. return sum
C (n) log n
Problem: Searching for key in a list of n items
Input size measure:
◦ Number of list’s items, i.e. n
Basic operation:
◦ Key comparison
Depends on form of input
Cworst(n) = n
Cbest(n) = 1
For some algorithms efficiency depends on form of
input:
Worst case: Cworst(n) – maximum over inputs of
size n
Best case: Cbest(n) – minimum over inputs of
size n
We will focus on worst-case analysis in this
course
◦ unless otherwise specified, you should always analyze
the worst case
there are many situations where:
best case = worst case
consider the algorithm to find the largest
element in an unordered array
For each of the following algorithms determine:
a) its basic operation
b) basic operation count
c) if basic op count depends on input form
1. computing the sum of a set of numbers
2. computing n! (n factorial)
3. check weather all the elements in a given
array are distinct
C(n) = n(n-1)/2
C(n) ≈ 0.5n2
C(n) = log n +5
C(n) = n!
Which one is better algorithm?
Value of function
fA(n) = n
fB(n) = n2
Increasing n
What we really care about:
◦ Order of growth as n→∞
consider table 2.1 from your textbookthese represent
possible functions
that classify basic
ops counts
it would take
more than 5
billion years
to make 100!
calculations*
* - on at 1000 MHz CPU
< < < < < <
This strategy is taken from page 62 of your textbook:
1. Decide on a parameter indicating the inputs size.
2. Identify the algorithms basic operation.
3. Check whether the number of times the basic operation is
executed depends only on the size of the input.
• if it depends on some other property, the best/worst/average
case efficiencies must be investigated separately
4. Set up a sum expressing the number of times the basic
operation is executed.
5. Use standard formulas and rules of sum manipulation to
find a closed form formula c(n) for the sum from step 4
above.
6. Determine the efficiency class of the algorithm using
asymptotic notations
A way of comparing functions
Big O
Big Θ
Big Ω
Set of all functions whose rate of
growth is the same as or lower than
that of g(n).
f(n) c * g(n) , for all n n0
Definition:
a function f(n) is in the set O(g(n)) [denoted: f(n)
O(g(n)) ] if there is a constant c and a positive
integer n0 such that
f(n) c * g(n) , for all n n0
ie: f(n) is bounded above by some constant
multiple of g(n)
f(n) = 2n+6 O(n)
?
definition:
◦ Need to find a constant c and a constant n0 such that
f(n) ≤ cg(n) for n>n0
c = 4 and n0=3
f(n) is O(n)
• Simple Rule: Drop lower order terms and constant
factors
1. 50n3 + 20n + 4 O(n3)
2. 4n2 + 10 O(n2)
3. n(2n +1) O(n2)
4. 3log n + 1 O(log n)
5. 3log n + n O(n)
6. 1+ log6 O(1)
7. 5! + 32 O(1)
Set of all functions whose rate of
growth is the same as or higher than
that of g(n).
f(n) c * g(n) , for all n n0
Definition:
a function f(n) is in the set Ω(g(n)) [denoted:
f(n) Ω(g(n)) ] if there is a constant c and a
positive integer n0 such that
f(n) c * g(n) , for all n n0
ie: f(n) is bounded below by some constant
multiple of g(n)
Set of all functions that
have the same rate of growth as g(n).
c2 g(n) ≤ f(n) ≤ c1 g(n) , for all n n0
Definition:
a function f(n) is in the set Θ(g(n)) [denoted: f(n)
Θ(g(n)) ] if there is some constants c1 and
c2, and a positive integer n0 such that
c2 g(n) ≤ f(n) ≤ c1 g(n) , for all n n0
ie: f(n) is bounded both above and below by
constant multiples of g(n)
Big-Oh is the one I will talk about the most
Why?
◦ Focuses on worst case efficiency
◦ Most common when people talk about algorithms
◦ If you understand one, then the rest are basically
the same
What is the order of the following:
10n O(n)
5n2+20 O(n2)
O(2n)
10000n + 2n
log(n) * (1+ n) O(nlog(n))
32
General Plan for Analysis
Decide on parameter n indicating input size
Identify algorithm’s basic operation
Determine worst and/or best cases for input of
size n
Set up a sum for the number of times the basic
operation is executed
Simplify the sum using standard formulas and
rules
Determine the efficiency class of the algorithm
using asymptotic notations
Problem: find the max element in a list
Input size measure:
◦ Number of list’s items, i.e. n
Basic operation:
◦ Comparison
n 1
C ( n) 1 n 1
i 1
Problem: Multiplication of two matrices
Input size measure:
◦ Matrix dimensions or total number of elements
Basic operation:
◦ Multiplication of two numbers
n 1 n 1 n 1
C (n) 1 = 𝑛3
i 0 j 0 k 0
Parameter for input size:
n, the size of the array
Basic operation:
Comparison in the innermost loop
Worst case efficiency count… nested loop:
ΣΣ 1 = Σ (n -1 – i -1 +1) Σ (n -1 – i)
n-2 n-1 n-2 n-2
=
i=0 J=i+1 i=0 i=0
Σ n -Σ 1 -Σ i
n-2 n-2 n-2
= = n(n-1) – (n-1) – (n-2)(n-1)/2
i=0 i=0 i=0
= n2 – n – n + 1 – n2/2 +3n/2 - 1
= n2/2 – n/2 ∈ O(n2)
1. Chapter 2.1, page 50, question 2
2. Chapter 2.2, page 60, question 5
3. Chapter 2.3, page 68, question 5,6
There will be a quiz in the lab next week.
It will be 5 questions, on D2L
◦ It will take 10-20 minutes
◦ Followed by a lab activity
