What is an Algorithm
An algorithm is all about the procedure with
the input and output
1
The Sort Problems
Input
A sequence of numbers <a1, a2, …,an>
Output
A permutation (reordering) of the input sequence
such that a’1 ≦a’2 ≦… ≦a’n
The Role of Algorithms in Computing 110/12/08 2
Correct Algorithms
A correct algorithm
Always produces the correct output for any input
For example:
Input <31,41,59,26,41,58>
>>>>>A correct algorithm<<<<<
<26,31,41,41,58,59>
The Role of Algorithms in Computing 110/12/08 3
What is an Algorithm?
A detail step by step instruction
Describe the instruction in words
What kind of computer programming languages?
Doesn’t matter
What kind of human spoken languages?
The language you like, even Chinese, Martian
Language
The Role of Algorithms in Computing 110/12/08 4
How to Solve the Sort
Algorithms?
Selection Sort
void selectionSort(int numbers[], int array_size)
{
int i, j, min;
for (i = 0; i < array_size-1; i++)
{
min = i;
for (j = i+1; j < array_size; j++)
{
if (numbers[j] < numbers[min])
min = j;
}
if(min!=i) swap(numbers[x],numbers[i]);
}
}
The Role of Algorithms in Computing 110/12/08 5
How to Solve the Sort
Algorithms? II
MergeSort
Separate the list into halves
Sort the two halves recursively
Merge the two sorted halves into one sorted list
The Role of Algorithms in Computing 110/12/08 6
Which one is better?
Better means
Time
Space
Generally focusing on the worst-case number
of comparisons required to solve the
problem.
The Role of Algorithms in Computing 110/12/08 7
Time Needed
Selection Sort
n-1, n-2, n-3, …., 1
O(c1n2)
Merge Sort
T(n)=T(n/2) + T(n/2) + cn
…
T(n)=O(c2nlog2n)
The Role of Algorithms in Computing 110/12/08 8
Time Needed
Merge Sort Wins
And Space?
The Role of Algorithms in Computing 110/12/08 9
Think about…
Two machine
Machine A: 109 per second instructions
Machine B: 106 per seconds instructions
Supposed c1=2, c2=50
We want to sort 102 integers
Which one runs faster?
We want to sort 106 integers
Which one runs faster?
The Role of Algorithms in Computing 110/12/08 10
Problems in the Computer?
The Human Genome Project
Identify 100,000 genes
Determine 3 billion chemical based pairs
Genes search between different human
The Role of Algorithms in Computing 110/12/08 11
Problems in the Computer?
Internet and the Web
IP route method.
Search Engine
Compress the data
How to store the password (RSA)
Network Security
Lots of problems
The Role of Algorithms in Computing 110/12/08 12
Problems in the Computer?
Manufacturing
Resources price
Human power price
Transportation price
Market
The place to set the
Factories
Warehouse
Stores
The Role of Algorithms in Computing 110/12/08 13
Applications in Computer
Hardware
GUI
Object-Oriented System
WAN, LAN
…
The Role of Algorithms in Computing 110/12/08 14
Thinks About
Program P1 solves a problem in n days.
Program P2 solves the same problem in 2n
seconds.
Q: Which one you will use?
A: Program P1 runs faster for n > 20.
The Role of Algorithms in Computing 110/12/08 15
Motivation
The rate of growth affects more.
We need notation to capture the concept of
“rate of growth” when we measure the time
and space efficiency of algorithms
The Role of Algorithms in Computing 110/12/08 16
Asymptotic Notation
Edmund Landau
1877~1938
Inventor of the asymptotic notation
Donald E. Knuth
1938 ~
Turing Award, 1974.
Father of the analysis of algorithms
Popularizing the asymptotic notation
The Role of Algorithms in Computing 110/12/08 17
Asymptotic Notation
Ο
Ω
Θ
The Role of Algorithms in Computing 110/12/08 18
Using Asymptotic Notation
in Sentences
Let n be the number of input integers
Program 1 takes time O(n)
It takes time O(n) for program 1 to solve the
problem
The time required by program 2 is O(2n)
O(n) reads?
Big-Oh of n
Order n
The Role of Algorithms in Computing 110/12/08 19
Meaning
Sentence
Program p2 takes time O(n) to solve the problem.
Means
The time needed by p2 is a function f(n) with
f(n)=O(n)
The Role of Algorithms in Computing 110/12/08 20
Meaning 2
Sentence
The comparison-based sort methods can not be
solved in O(n) time.
Means
The comparison-based sort problems can not be
solved in h(n) time, for any function h(n) with
h(n)=O(n)
The Role of Algorithms in Computing 110/12/08 21
f(n)=O(g(n))
Intuitive meaning
f(n) does not grow faster then g(n)
Comments
f(n)=O( g(n) ) roughly means f(n) ≦ g(n) in terms
of rate of growth
= is not the meaning of equation. It’s more like
We do not write O(g(n))=f(n)
The Role of Algorithms in Computing 110/12/08 22
Formal Definition of O
For any two functions f(n) and g(n), we write
f(n)=O(g(n))
If there exists positive constants n0 and c such
that the inequality f(n) ≦c g(n)
holds for each integer n ≧ n0
The Role of Algorithms in Computing 110/12/08 23
In Other Words
The definition of f(n)=O(g(n)) states that
there exists a positive constant c such that
the value of f(n) is upper-bounded by cg(n)
for all sufficiently large positive integers n.
The Role of Algorithms in Computing 110/12/08 24
Questions
n=O(n)?
999n=O(n)?
5n2=O(n3-n2)?
n2=O(n)?
The Role of Algorithms in Computing 110/12/08 25
n=O(n)?
Yes, for n0=1 and c=1
n ≦ 1n , for n ≧ 1
The Role of Algorithms in Computing 110/12/08 26
999n=O(n)?
Yes, for n0=1, c=999
999n ≦ 999n , for n ≧ 1
The Role of Algorithms in Computing 110/12/08 27
5n2=O(n3-n2)?
Yes, let n0=2, c=5
5n2≦5(n3-n2)
5n2 ≦ 5n3-5n2
10n2≦ 5n3
2≦ n
The Role of Algorithms in Computing 110/12/08 28
n2=O(n)?
Is n can be the upper-bound of n2
Instinctive feeling: NO
How to proof?
Contradiction Method
The Role of Algorithms in Computing 110/12/08 29
Proof
Assume for a contradiction that there exists
constants c and n0 such that
n2≦cn
holds for any integer n with n ≧ n0. n is an
arbitrary integer strictly larger than
max(n0,c).
For instance, let n = 1+max(n0,c)
n2>cn (n>c), contradiction.
The Role of Algorithms in Computing 110/12/08 30
Other Notations
Big-Oh only gives the upper bounds. We need
other asymptotic notations.
f(n)=O(g(n)) f(n) ≦ g(n) in rate of growth
f(n)=Ω(g(n)) f(n) ≧ g(n) in rate of growth
f(n)=Θ(g(n)) f(n) ＝ g(n) in rate of growth
f(n)=o(g(n)) f(n) ＜ g(n) in rate of growth
f(n)= ω(g(n)) f(n) ＞ g(n) in rate of growth
The Role of Algorithms in Computing 110/12/08 31
Omega
Definition [Omega]
f(n) = Ω(g(n)) iff there exist positive constants
c and n0 such that f(n) ≥ cg(n) for all n, n ≥ n0.
The function g(n) is only a lower bound on f(n).
f(n) = Ω(g(n)) to be informative, g(n) should be
as large a function of n as one can come up
with for which f(n) = Ω(g(n)) is true.
CH1: Basic Concepts 110/12/08 32
Theta
Definition [Theta]:
f(n) = Θ(g(n)) iff there exist positive constants
c1, c2 and n0 such that c1g(n) ≤ f(n) ≤ c2g(n) for
all n, n ≥ n0.
Lower bound and upper bound on f(n)
The theta notation is more precise than
both “big oh” and omega notations.
CH1: Basic Concepts 110/12/08 33
Comparing Two Algorithms
We say that Algorithm A is no worse than
Algorithm B in terms of worst-case time
complexity if there exists a positive function
f(n) such that
Algorithm A runs in time O(f(n)) and
Algorithm B runs in time Ω(f(n)) in the worst case
The Role of Algorithms in Computing 110/12/08 34
Comparing Two Algorithms
(2)
Algorithm A is strictly better than algorithm B
in terms of worst-case time complexity if
there exists a positive function f(n) such that
Algorithm A runs in time O(f(n)) and
Algorithm B runs in time ω (f(n)) in the worst case
OR
Algorithm A runs in time o(f(n)) and
Algorithm B runs in time Ω (f(n)) in the worst case
The Role of Algorithms in Computing 110/12/08 35
Tightness in Analysis
Supposed we figure out that the time
complexity of a algorithm is O(f(n)). We say
that the analysis is tight if the algorithm runs
in Ω(f(n)) in the worst case.
In others words, if the time complexity of the
algorithm is O(f(n)) and the analysis is tight,
then the time complexity of the algorithm is
Θ(f(n))
The Role of Algorithms in Computing 110/12/08 36
Time Optimal Algorithm
We say that Algorithm A is a optimal
algorithm for a problem P in terms of worst-
case time complexity if
Algorithm A runs in time O(f(n)) and
Any algorithm that solves the problem P requires
time Ω(f(n)) in the worst case.
The Role of Algorithms in Computing 110/12/08 37
