History
Derived from the term algorism, the origin of the term is attributed
to Persian astronomer and mathematician,
Abu Abdullah Muhammad ibn Musa Al-Khwarizmi (c. 850 AD).
Example Chocolate Cream Pie
1. Heat milk, marshmallows and chocolate in 3-quart saucepan over low
heat, stirring constantly, until chocolate and marshmallows are melted
and blended. Refrigerate about 20 minutes, stirring occasionally until
mixture mounds slightly when dropped from a spoon.
2. Beat whipping cream in chilled small bowl with electric mixer on high
speed until soft peaks form. Fold chocolate mixture into whipped cream.
Pour into pie shell. Refrigerate uncovered about 8 hours or until set.
Garnish with milk chocolate curls and whipped cream.
Example
[Link] the oil pan underneath the oil plug of your car.
[Link] the oil plug.
[Link] oil.
[Link] the oil plug.
[Link] the oil cap from the engine.
[Link] in 4 quarts of oil.
[Link] the oil cap.
Understanding
• An algorithm is an outline of the steps that a program or any computational
procedure has to take.
• Through the use of algorithms, we can make computers "intelligent" by
programming them with various algorithms to solve problems. The speed
and accuracy of computers are well-suited for solving tedious problems
Definition
An algorithm is a well-ordered collection of unambiguous and effectively
computable operations that when executed produces a result and halts in a
finite amount of time
Problem Vs Program
Qualities of a good algorithm
1. Input and output should be defined precisely.
2. Each step in the algorithm should be clear and unambiguous.
3. Algorithms should be most effective among many different ways to solve a
problem.
4. An algorithm shouldn't have a computer code. Instead, the algorithm should
be written in such a way that it can be used in different programming
languages.
Common Elements of Algorithms
• acquire data (input) some means of reading values from an external source; most
algorithms require data values to define the specific problem (e.g., coefficients of a
polynomial)
• computation some means of performing arithmetic computations, comparisons, testing
logical conditions, and so forth...
• selection some means of choosing among two or more possible courses of action, based
upon initial data, user input and/or computed results
• iteration some means of repeatedly executing a collection of instructions, for a fixed number
of times or until some logical condition holds
• report results (output) some means of reporting computed results to the user, or requesting
additional data from the user
Properties of an Algorithm
• finiteness: The algorithm must always terminate after a finite number of steps.
• definiteness: Each step must be precisely defined; the actions to be carried out
must be rigorously and unambiguously specified for each case.
• input: An algorithm has zero or more inputs, taken from a specified set of
objects.
• output: An algorithm has one or more outputs, which have a specified relation to
the inputs.
• effectiveness: All operations to be performed must be sufficiently basic that they
can be done exactly and in finite length.
How to express an algorithm?
• natural language : usually verbose and ambiguous
• flow chart: avoid most (if not all) issues of ambiguity; difficult to
modify w/o specialized tools; largely standardized
• pseudo-code: more structured than usual prose but less formal than a
programming language, also avoids most issues of ambiguity
Natural language
Step 1:
Start
Step 2:
Declare variables a,b and c.
Step 3:
Read variables a,b and c.
Step 4:
If a > b
If a > c
Display a is the largest number.
Else
Display c is the largest number.
Else
If b > c
Display b is the largest number.
Else
Display c is the greatest number.
Step 5: Stop
Pseudocode
Algorithm arrayMax(A, n):
Input: An array A storing n integers.
Output: The maximum element in A.
currentMax:= A[0]
for i:= 1 to n −1 do
if currentMax < A[i] then
currentMax:= A[i]
return currentMax
Flowchart
Exercise
1. Write your last name at the top of a sheet of paper
2. If you last name begins with 'H', go to step 4 or step 5
3. Draw something.
4. Write the weather for May 4, 2032 under your last name.
5. Go back to step 1.
Analysis of Algorithm
• gauge the efficiency of the algorithm.
• To evaluate rigorously the resources needed by an algorithm
and represent the result of the evaluation with a formula
How to measure efficiency?
Two different ways:
• space efficiency
• time efficiency.
• An algorithm that is space-efficient uses the least amount of computer memory to
solve the problem.
• An algorithm that is time-efficient uses the least amount of time to solve the problem
• Time complexity : running time of an algorithm is stated as a function
relating the input length to the number of steps
• Space complexity : function of volume of memory
Space Complexity
Space complexity of an algorithm represents the amount of memory space required by the
algorithm in its life cycle.
The space required by an algorithm is equal to the sum of the following two components:
1) A fixed part that is a space required to store certain data and variables, that are
independent of the size of the problem. For example, simple variables and constants
used, program size, etc.
2) A variable part is a space required by variables, whose size depends on the size of the
problem. For example, dynamic memory allocation, recursion stack space, etc.
Space complexity S(P) of any algorithm P is S(P) = C + S(I), where C is the fixed part and
S(I) is the variable part of the algorithm,
Example
Algorithm: SUM(A, B)
Step 1 - START
Step 2 - C ← A + B + 10
Step 3 - Stop
Here we have three variables A, B, and C and one constant. Hence S(P) = 1 + 3.
Time Complexity
• Time complexity of an algorithm represents the amount of time required by
the algorithm to run to completion. Time requirements can be defined as a
numerical function T(n), where T(n) can be measured as the number of
steps, provided each step consumes constant time.
• For example, addition of two n-bit integers takes n steps. Consequently,
the total computational time is T(n) = c ∗ n, where c is the time taken for
the addition of two bits.
Types of Analysis
APosterior Analysis:
• This is an empirical analysis of an algorithm.
• The selected algorithm is implemented using programming language.
• Actual statistics like running time and space are collected.
• Same hardware and software environments should be used.
APriori Analysis:
• This is a theoretical analysis of an algorithm.
• Efficiency of an algorithm is evaluated independent of the hardware and
software environment.
Types of Analysis
• Worst case
• Provides an upper bound on running time (Maximum time required for program execution)
• An absolute guarantee that the algorithm would not run longer, no matter what the inputs
are
• Best case
• Provides a lower bound on running time (Minimum time required for program execution)
• Input is the one for which the algorithm runs the fastest
Lower Bound Running Time Upper Bound
• Average case
• Provides a prediction about the running time (Average time required for program execution)
• Assumes that the input is random
Asymptotic Analysis
• To compare two algorithms with running times f(n) and g(n), we need a
rough measure that characterizes how fast each function grows.
• Hint: use rate of growth
• Compare functions in the limit, that is, asymptotically!
(i.e., for large values of n)
Rate of Growth
• Consider the example of buying elephants and goldfish:
Cost: cost_of_elephants + cost_of_goldfish
Cost ~ cost_of_elephants (approximation)
• The low order terms in a function are relatively insignificant for large n
n4 + 100n2 + 10n + 50 ~ n4
i.e., we say that n4 + 100n2 + 10n + 50 and n4 have the same rate of growth
Asymptotic notations
Following are the commonly used asymptotic notations to calculate the
running time complexity of an algorithm.
• Ο Notation
• Ω Notation
• θ Notation
Big Oh Notation, Ο
• The notation Ο(n) is the formal way to express the upper bound of an algorithm's running time.
f(n)= O(g(n)) if there exists a positive integer n0 and a positive
constant c such that f(n) ≤ c.g(n), for all n ≥ n0.
Example: 2n + 10 is O(n)
2n + 10 cn
(c 2) n 10
n 10/(c 2)
Pick c = 3 and n0 = 10
More Big-Oh Examples
7n-2
7n-2 is O(n)
need c > 0 and n0 1 such that 7n-2 c•n for n n0
this is true for c = 7 and n0 = 1
3n3 + 20n2 + 5
3n3 + 20n2 + 5 is O(n3)
need c > 0 and n0 1 such that 3n3 + 20n2 + 5 c•n3 for n n0
this is true for c = 4 and n0 = 21
3 log n + 5
3 log n + 5 is O(log n)
need c > 0 and n0 1 such that 3 log n + 5 c•log n for n n0
this is true for c = 8 and n0 = 2
Big-Oh Rules
• If is f(n) a polynomial of degree d, then f(n) is O(nd), i.e.,
[Link] lower-order terms
[Link] constant factors
• Use the smallest possible class of functions
• Say “2n is O(n)” instead of “2n is O(n2)”
• Use the simplest expression of the class
• Say “3n + 5 is O(n)” instead of “3n + 5 is O(3n)”
Omega Notation, Ω
The notation Ω(n) is the formal way to express the lower bound of an algorithm's running time.
f(n)= Ω(g(n)) if there exists a positive integer n0 and a positive
constant c such that f(n) ≥ c.g(n), for all n ≥ n0.
Example
Let us consider a given function, f(n)=4n3+10n2+5n+1.
Considering g(n)=n3, f(n)⩾4.g(n) for all the values of n>0.
Hence, the complexity of f(n) can be represented as Ω(g(n)), i.e. Ω(n3)
Theta Notation, θ
The notation θ(n) is the formal way to express both the lower bound and the upper bound of an algorithm's
running time
f(n)=θ(g(n)) if there exists a positive integer n0 and positive constants
c1 and c2 that c1.g(n)⩽f(n)⩽c2.g(n) for all n ≥ n0.
Example
Let us consider a given function, f(n)=28n+9
Considering g(n)=n, 27g(n)⩽f(n)⩽37g(n) for of n>0.
Hence, the complexity of f(n) can be represented as θ(g(n)),
i.e. θ(n)
Big Oh: Common Categories
From fastest to slowest
Name Big-O
Constant O(1)
Logarithmic O(log(n))
Linear O(n)
Log Linear O(n log(n))
2
Quadratic Ο(n )
3
Cubic Ο(n )
n
Exponential O(2 )
Constant Time: O(1)
Properties of an algorithm with constant time complexity:
• Algorithm execution time is not dependent on the size of the input
data
• Time complexity is always the same, regardless of input
Example
c=a+b;
Logarithmic Time: O(log n)
Properties of an algorithm with logarithmic time complexity:
• Reduces the size of the input data in each step
• The next action will only be performed on one of several possible
elements
Example : Print every third value in a range
for (i=0; i<N;i=i+3)
print(data[i])
Linear Time: O(n)
Properties of an algorithm with linear time complexity:
• Number of operations taking place scales linearly with the size of n
• e.g. Performing the print operation 100 times, once per item, in a list
containing 100 items
for (i=0; i<N;i++)
print(data[i])
Quasilinear Time: O(n log n)
Properties of an algorithm with log linear (also known as quasilinear) time
complexity:
• Each operation in the input data has a logarithm time complexity
Example
Now in Quick Sort, we divide the list into halves every time, but we repeat the
iteration N times(where N is the size of list). Hence time complexity will be
N*log( N ). The running time consists of N loops (iterative or recursive) that are
logarithmic, thus the algorithm is a combination of linear and logarithmic.
Quadratic Time: O(n²)
Properties of an algorithm with quadratic time complexity:
• Perform a linear time operation for each value in the input data
• For a list of n items, we perform n operations for each item. e.g. 10
items has 10^2 operations.
Example
for(i=0; i < N; i++)
{
for(j=0; j < N;j++)
{
print j
}
}
Exponential Time: O(2^n)
Properties of an algorithm with exponential time complexity:
• Growth doubles with each addition to the input data set
• Examples of exponential runtime algorithms:
Example
Power Set: finding all the subsets on a set.
Fibonacci.
powerset('') // => ['']
powerset('a') // => ['', 'a']
powerset('ab') // => ['', 'a', 'b', 'ab']
True or false?
1. 4+3n is O(n)
2. n+2 logn is O(log n)
3. logn+2 is O(1)
4. n50 is O(1.1n)
Exercise -1
Algorithm prefixAverages1(X, n)
Input array X of n integers
Output array A of prefix averages of X
A new array of n integers
for i 0 to n 1 do
s X[0]
for j 1 to i do
s s + X[j]
A[i] s / (i + 1)
return A
Exercise -2
for i=20 to 30
for j=1 to n
x=x+1
end
end