LECTURE 02
BASICS OF ALGORITHM DESIGN & ANALYSIS
GROWTH OF FUNCTION
1
Pseudocode
High-level description of an algorithm
More structured than English prose
Less detailed than a program
Preferred notation for describing algorithms
Hides program design issues
Use indentation to determined statement blocks
2
Pseudocode
Programming Constructs:
Expressions (to express numeric and Boolean
expression)
Method declarations: Algorithm name(param1,
param2…)
Decision structures: if…then…[else…]
While loops: while…..do….
Repeat loops: Repeat…until….
For loop: for….do…..
Array indexing: A[i], A[i,j]
Functions:
Calls: return_type function_name(param1, param2…)
Returns: return value
3
Pseudocode example
Example: find max element of an array
Algorithm arrayMax(A,n)
Input array A of n integers
Output maximum element of A
currentMax A[0]
for i 1 to n 1 do
if A[i] currentMax then
currentMax A[i]
increment i
return currentMax
4
Primitive Operations
Basic computations performed by an algorithm
Identifiable in pseudocode
Largely independent from the programming
language
Exact definition not important (we will see why
later)
Assumed to take a constant amount of time
5
Primitive operation examples
Performing an arithmetic operation or logical
expression (e.g.: comparing two numbers)
Assigning a value to a variable (data movement)
Indexing into an array
Calling a method
Returning from a method
6
Algorithm Analysis
Let T(N) = running time, where N (sometimes n) = size of
input
Linear or binary search
Sorting
Multiplication
Traversing a graph etc
T(N) measures number of primitive operations performed
Certain pattern must be defined
Running time calculations:
The declarations count for no time
Simple operations (e.g. +, *, <=, =) count for one unit
each
Return statement counts for one unit
7
Counting Primitive Operations
By inspecting the pseudocode, we can determine the
maximum number of primitive operations executed by
an algorithm, as a function of the input size
Algorithm arrayMax(A,n) # operations
currentMax A[0] 2
for i 1 to n 1 do 1+n
if A[i] currentMax then 2(n-1)
currentMax A[i] 2(n-1)
increment i 2(n-1)
return currentMax 1
Total: 7n-2 8
General Rules
Algorithm (Loops) #operations
for i 0 to (n-1) do 1+n
sum+= i * i 3*n
Total: 4n+1
Running time of the statement inside the loop: Running time of the
statement times the number of iterations of the loop
Algorithm (Nested Loops) #operations
for i 0 to (n-1) do 1+n
for j 0 to (n-1) do n*(1+n)
sum++ n*n
Total: 2n2+2n+1
Running time of the statement inside a group of nested loop is the running
time of the statement multiplied by the product of the sizes of all the loops
9
General Rules
Algorithm #operations
x, y, z, count = 0 1
for (x=n/2; x<=n; x++) n
for (y=1; y+(n/2)<=n; j++)
for (z=1; z<= n; z=z*2)
count++
No of Increment
iteration pattern of x
1 (n/2)+0
2 (n/2)+1 (n/2)+(k-1) = n
k-1 = n-(n/2)
3 (n/2)+2 Thus, k = (n/2)+1
4 (n/2)+3
k (n/2)+(k-1)
10
General Rules
Algorithm #operations
x, y, z, count = 0 1
for (x=n/2; x<=n; x++) n
for (y=1; y+(n/2)<=n; y++) n
for (z=1; z<= n; z=z*2)
count++
No. of Iteration Increment
pattern of y
1 1
2 2
3 3
4 4
y+(n/2)<=n, j=k=n/2
y<=n-(n/2)=n/2 11
General Rules
Algorithm #operations
x, y, z, count = 0 1
for (x=n/2; x<=n; x++) n
for (y=1; y+(n/2)<=n; y++) n*n
for (z=1; z<= n; z=z*2) n*n*log2 n
count++ n*n*log2 n
T(n) O(n2log2 n)
No. of Iteration Increment pattern of z
1 1
2 2
3 3
4 4
k 2(k-1) = n;
Log2 n + 1 12
General Rules
Conditional statements: running time of the test + if or else (various blocks
of conditionally executed statements that has the largest running time)
Algorithm #operations
if (n==0) then 1
a[j] = 0 1+1
else
for i 1 to n do 1+n
a[j] += a[j] + i * j n(1+1+1+1)
Total: 5n+4
13
General Rules
Logarithm complexity: when the problem size is cut
down by a fraction
No of Increment Rewrite the
Algorithm Iteration pattern of i increment
pattern of i
for i 1 to (n) do
1 2 21
i=i*2
2 4 22
3 8 23
4 16 24
5 32 25
k … 2(k-1)
To know how many iteration, i.e. k, we need to use log.
Thus, k-1 = log2 n, k = log2 n + 1
14
General Rules
Logarithm complexity
Algorithm No of Increment
for i n to (1) do Iteration pattern of i
i = i /2
1 n/20
2 n/21
3 n/22
( )
4 n/23
( )
k n/2(k-1)=1
Interestingly, we get the similar function as the
previous algorithm, i.e. k-1 = log2 n, k = log2 n + 1
15
General Rules
While loop
Algorithm #operations
i = 1, k = 1 1
k=k+i means that k=1+2;
while(k <= n) do √n k=(1+2)+3
i++ √n k=(1+2+3)+4……
Summation formula:
k = k+i √n z(z+1)/2
Thus, z2+z <=2n
Take the biggest operation: z2
<=2n
z = √2n=√2*√n
Ignore the constant, z = √n
k 1 3 6 10 15 x
i 1 2 3 4 5 z
16
Estimating Running Time
Algorithm arrayMax executes 7n2 primitive
operations in the worst case whereby the ‘if’ loop is
always true.
Algorithm arrayMax executes 5n primitive operations
in the best case whereby the ‘if’ loop is always false.
Let T(n) be worst-case time of arrayMax. Then
T(n) = 7n 2
17
Growth Rate of Running Time
Changing the hardware/software environment
Affects T(n) by a constant factor, but
Does not alter the growth rate of T(n)
The linear growth rate of the running time T(n) is an
intrinsic property of algorithm arrayMax
18
n log n n n log n n2 n3 2n
4 2 4 8 16 64 16
8 3 8 24 64 512 256
16 4 16 64 256 4,096 65,536
32 5 32 160 1,024 32,768 4,294,967,296
64 6 64 384 4,094 262,144 1.84 * 1019
128 7 128 896 16,384 2,097,152 3.40 * 1038
256 8 256 2,048 65,536 16,777,216 1.15 * 1077
512 9 512 4,608 262,144 134,217,728 1.34 * 10154
1024 10 1,024 10,240 1,048,576 1,073,741,824 1.79 * 10308
19
If the numbers below are in terms of micro seconds:
n log n n n log n n2 n3 2n
4 2 4 8 16 64 16
8 3 8 24 64 512 256
16 4 16 64 256 4,096 65,536
32 5 32 160 1,024 32,768 4,294,967,296
64 6 64 384 4,094 262,144 1.84 * 1019
128 7 128 896 16,384 2,097,152 3.40 * 1038
256 8 256 2,048 65,536 16,777,216 1.15 * 1077
512 9 512 4,608 262,144 134,217,728 1.34 * 10154
1024 10 1,024 10,240 1,048,576 1,073,741,824 1.79 * 10308
1s 18 mins 5.67 * 10288 yrs
20
Growth Rates of Functions
From lowest to highest:
Constant 1
Logarithmic log n
Linear n
N-Log-N n log n
Quadratic n2
Cubic n3
Exponential 2n
21
22
Constant Factors
1E+26
1E+23 Quadratic Quadratic Linear Linear
1E+20
1E+17
T(n)
1E+14
1E+11
1E+8
1E+5
1E+2
1E-1
1E-1 1E+1 1E+3 n 1E+5 1E+7 1E+9
Recall that the growth rate is not affected by constant
factors or lower-order terms
Examples
102n + 105 is a linear function
105n2 + 108n is a quadratic function
23
Asymptotic Notation
Our concern:
How running time/number of operations scales with
the size of the input (i.e. the runtime’s rate of
growth)
To measure the runtime independent from
hardware, programming language, etc
Use asymptotic notation to represent the growth of
the function after dropping the constant coefficients
and less significant terms
24
Asymptotic Notation
Commonly focus on this
Three forms: since it deals with any
Worse-case: Big O kind of input
The runtime on the worst possible input
Best-case: Big Omega
The runtime on the best possible input
Average-case: Big Theta If randomized algorithm,
The runtime on the average input then we prefer this
Asymptotic more efficient: best for all but small
sample size n
25
Big-Oh Defined
The O symbol was introduced in 1927 to indicate
relative growth of two functions based on asymptotic
behaviour of the functions
Now used to classify functions and families of
functions
When T(n) is O(f(n): if and only if T(n) is eventually
upper bounded by a constant of multiple of f(n)
Upper Bounded
26
Big-Oh Defined
Using mathematic to explain:
“Given functions T(n) and f(n), we say that
T(n) is O(f(n)) if and only if there exist
positive constants
c and n0 such that for all n n0,T(n) c.f(n)”
c is the constant factor
n0 is the starting input value
T(n) is O(f(n))
It means that the growth rate of
T(n) is not more than O(f(n))
27
c*f(n)
c*f(n) is an upper bound for T(n)
T(n)
Asymptotic upper bound
n0 n
T(n) = O(f(n)) if there are constants c and n0
such that T(n) < c*f(n) when n n0
28
Big-Oh Defined
Proof that 7n – 2 = O(n)
7n – 2 <= cn for all n>= n0
n(7-c) <= 2 (or you can move to RHS: cn – 7n = n(c-7))
Let’s choose c = 6, n0 = 1
1(1)<= 2 ~ proof Another way to proof:
7n – 2 <= cn for n>= n0
Try this:
This is true when c = 7, n0 = 1
3n2 + 5n <= cn2
7(1)-2 <= 7(1) ~ proof
29
Proper proof procedures:
Let c = 6, n0 = 1. We will now show that 7n – 2 <= cn
for all n>= n0
We now that for any n>= n0 we have:
1 <= n (i.e. n0 <=n)
7n-2 <= 6n
Using our choice of c and n0, we have successfully
shown that 7n – 2 <= cn for all n>= n0 . From the
definition of Big-O, this proves that 7n – 2 = O(n)
30
Big-Oh Notation
Example: 2n + 10 is O(n)
2n + 10 cn 10,000
(c 2) n 10 3n
2n+10
n 10/(c 2) n
1,000
Pick c = 3 and n0 = 10
100
10
1
1 10 100 1,000
n 31
Big-Oh Example
Example: the function n2 is not O(n)
n2 cn 1,000,000
n c n^2
100n
100,000 10n
The above inequality n
cannot be satisfied since 10,000
c must be a constant
1,000
100
10
1
1 10 100 1,000
n 32
Big-Oh Rules
If f(n) is a polynomial of degree d, then f(n) is O(nd),
i.e.,
Drop lower-order terms
Drop constant factors
Use the smallest possible class of functions
(characterize a function as closely as possible)
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)”
To simplify the running time estimation, for a function
f(n), we drop leading constants and delete lower order
terms.
33
Exercise
Big-Oh examples
7n-2 is ____________
3n3 + 20n2 + 5 is ____________
3 log n + 5 is ____________
10000n + 5 is ____________
34
Exercise
f(n) = 8n2…..is it O(n)?
f(n) = 50n3 + 20n + 4 ….. is it O(n3)?
f(n) = 50n3 + 20n + 4 ….. is it O(n5)?
f(n) = 50n3 + 20n + 4 ….. is it O(n3+n)?
35
Asymptotic Algorithm Analysis
The asymptotic analysis of an algorithm determines
the running time in big-Oh notation
To perform the asymptotic analysis
We find the worst-case number of primitive
operations executed as a function of the input size
We express this function with big-Oh notation
Example:
We determine that algorithm arrayMax executes at
most 7n 3 primitive operations
We say that algorithm arrayMax “runs in O(n) time”
Since constant factors and lower-order terms are
eventually dropped anyhow, we can disregard them
when counting primitive operations 36
Asymptotic Algorithm Analysis
Since constant factors and lower-order terms are
eventually dropped anyhow, we can disregard them
when counting primitive operations
Algorithm arrayMax(A, n) # operations
currentMax A[0] 1
for i 1 to n 1 do n
if A[i] currentMax then n
currentMax A[i] n
increment i n
return currentMax 1
Total: O(n)
37
The Importance of Asymptotics
An algorithm with an asymptotically slow running time
is beaten in the long run by an algorithm with an
asymptotically faster running time
Maximum Problem Size (n)
Running Time 1 second 1 minute 1 hour
O(n) 2,500 150,000 9,000,000
O(n[log n]) 4,096 166,666 7,826,087
O(n2) 707 5,477 42,426
O(n4) 31 88 244
O(2n) 19 25 31
38
Big-Oh and Growth Rate
The big-Oh notation gives an upper bound on the
growth rate of a function
The statement “f(n) is O(g(n))” means that the growth
rate of f(n) is no more than the growth rate of g(n)
We can then use the big-Oh notation to rank functions
according to their growth rate
f(n) is O(g(n)) g(n) is O(f(n))
g(n) grows more Yes No
f(n) grows more No Yes
Same growth Yes Yes
39
Growth Rate of Running Time
Consider a program with time complexity O(n2).
For the input of size n, it takes 5 seconds.
If the input size is doubled (2n), then it takes 20
seconds.
Consider a program with time complexity O(n).
For the input of size n, it takes 5 seconds.
If the input size is doubled (2n), then it takes 10
seconds.
Consider a program with time complexity O(n3).
For the input of size n, it takes 5 seconds.
If the input size is doubled (2n), then it takes 40
seconds.
40
Computing Prefix Averages
We further illustrate asymptotic 35
analysis with two algorithms for prefix X
averages 30 A
The i-th prefix average of an array X
is average of the first (i + 1) elements 25
of X:
A[i] = (X[0] + X[1] + … + X[i])/(i+1) 20
OR
15
10
5
Computing the array A of prefix
averages of another array X has 0
applications to financial analysis 1 2 3 4 5 6 7
41
Prefix Averages (Quadratic)
The following algorithm computes prefix averages in
quadratic time by applying the definition
Algorithm prefixAverages1(X, n)
Input array X of n integers
Output array A of prefix averages of X #operations
A new array of n integers 1
for i 0 to n 1 do n
s X[0] n
for j 1 to i do 1+2+…+(n1)
s s + X[j] 1+2+…+(n1)
A[i] s / (i + 1) n
return A 1
T(n) = O(n2)
42
Prefix Averages (Quadratic)
i X[i] A[i] – array of prefix averages of X
0 11 (11)/1 = 11
1 23 (11+23)/2 = 17
2 5 (11+23+5)/3 = 13
3 27 (11+23+5+27)/4 = 16.5
4 33 (11+23+5+27+33)/5 = 19.8
5 1 (11+23+5+27+33+1)/6 = 16.67
6 45 (11+23+5+27+33+1+45)/7 = 20.7
7 18 (11+23+5+27+33+1+45+18)/8 = 20.4
43
Arithmetic Progression
The running time of 7
prefixAverages1 is 6
O(1 + 2 + …+ n)
5
The sum of the first n
integers is n(n + 1) / 2 4
There is a simple 3
visual proof of this 2
fact
1
Thus, algorithm
prefixAverages1 runs 0
in O(n2) time 1 2 3 4 5 6
44
Arithmetic Progression
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
= (1+10) + (2+9) + (3+8) + (4+7) + (5+6)
= (1+10) × (10/2)
1 + 2 + 3 + 4 + 5 + ………..+ n
= (1+n) × (n/2)
= n(n+1)/2
= O(n2)
45
Prefix Averages (Linear)
The following algorithm computes prefix averages in
linear time by keeping a running sum
Algorithm prefixAverages2(X,n)
Input array X of n integers
Output array A of prefix averages of X #operations
A new array of n integers 1
s 0 1
for i 0 to n 1 do n
s s + X[i] n
A[i] s / (i + 1) n
return A 1
T(n) = O(n)
46
Prefix Averages (Linear)
i X[i] s A[i] – array of
prefix averages of
X
0 11 0+11=11 11/1=11
1 23 11+23=34 34/2=17
2 5 34+5=39 39/3=13
3 27 39+27=66 66/4=16.5
4 33 66+33=99 99/5=19.8
5 1 99+1=100 100/6=16.67
6 45 100+45=145 145/7=20.7
7 18 145+18=163 163/8=20.4
47
Applying Asymptotic Analysis
How would the table below change if the hardware
used was 150 times faster? Assume the original m is
500,000 basic operations in one hour. What would be
the new maximum problem size? 500,000*150 =
Maximum Problem Size (n) 75,000,000
Running Time Original New n value
O(n) 500,000 75,000,000
O(n[log n]) ≈33,333 ≈3570000
O(n2) √500,00 ≈8660
0 ≈ 707
O(n4) 4√500,0
00 ≈93
≈26.5 m
O(2n) ≈18.9 Log(75,000,000)≈26 48
Relatives of Big-Oh
Big-Omega
f(n) is Ω(g(n)) if there is a constant c > 0 and an
integer constant n0 ≥ 1 such that f(n) ≥ c.g(n) for n ≥
n0. 3nlogn + 2n is Ω(nlogn)
Since: 3nlogn + 2 ≥ nlogn, for n ≥ 2
49
Relatives of Big-Oh
Big-Theta (tight bound)
f(n) is Θ(g(n)) if there are constant c’ > 0 and c’’ > 0
an integer constant n0 ≥ 1 such that c’.g(n)≤f(n)
≤c’’.g(n) for n ≥ n0.
3nlogn + 4n + 5logn is Θ(nlogn)
Since: 3nlogn ≤ 4n+ 5logn ≤
(3+4+5) nlogn, for n ≥ 2
50
Intuition for Asymptotic Notation
Big-Oh f(n) is O(g(n)) if f(n) is asymptotically less
than or equal to g(n)
Big-Omega f(n) is (g(n)) if f(n) is asymptotically
greater than or equal to g(n)
Big-Theta f(n) is (g(n)) if f(n) is asymptotically
equal to g(n)
Little-oh f(n) is o(g(n)) if f(n) is asymptotically
strictly less than g(n)
Little-omega f(n) is (g(n)) if is asymptotically
strictly greater than g(n)
51
Example Uses of the Relatives of Big-Oh
5n2 is (n2)
f(n) is (g(n)) if there is a constant c > 0 and an integer
constant n0 1 such that f(n) c•g(n) for n n0
let c = 5 and n0 = 1
5n2 is (n)
f(n) is (g(n)) if there is a constant c > 0 and an integer
constant n0 1 such that f(n) c•g(n) for n n0
let c = 1 and n0 = 1
5n2 is (n)
f(n) is (g(n)) if, for any constant c > 0, there is an
integer constant n0 0 such that f(n) c•g(n) for n n0
need 5n02 c•n0 given c, the n0 that satisfies this is
n0 c/5 0
52
Example Uses of the Relatives of Big-Oh
5n2+3nlogn+2n+5 is O(n2)
5n2+3nlogn+2n+5 ≤ (5+3+2+5)n2 = cn2 for c = 15, n0=2
3nlogn +2n is Ω(nlogn)
f(n) is Ω(g(n)) if there is a constant c > 0 and an integer
constant n0 1 such that f(n) c•g(n) for n n0
let c=3 and n0 = 2
5n2 is omega(n)
f(n) is Ω(g(n)) if there is a constant c > 0 and an integer
constant n0 1 such that f(n) c•g(n) for n n0
let c=1 and n0 = 1
3nlogn+4n+5 is Θ(nlogn)
3nlogn≤ 3nlogn+4n+5 ≤(3+4+5) nlogn for n 2
53
Example through Formal Proof
Show that
1. Get positive constant c1, c2 and no
for all
By eliminate , . If n is 6, we get 0, c1 is a
negative, but c1 must be positive. In order to fulfil the
condition, the minimum value of n must be 10
54
Time Complexity
Time complexity refers to the use of asymptotic
notation (O, , , o, ) in denoting running time
If two algorithms accomplishing the same task belong
to two different time complexities:
One will be faster than the other
As n is increased further, more benefit will be
gained from the faster algorithm
Faster algorithm is generally preferred
55
Time Complexity Comparison
A fast algorithm has a small time complexity, while a
slow algorithm has large time complexity.
Comparison of algorithm speed
Constant 1 (fastest)
Logarithmic log n
Linear n
N-Log-N n log n
Quadratic n2
Cubic n3
Exponential 2n (slowest)
56
Exercise
Which is these is TRUE/FALSE
N2 = O(N2)
2N = O(N2)
N = O(N2)
N2 = O(N)
2N = O(N)
N = O(N)
57
Rules of Thumb to Find Complexity
A small number of simple statements in a program – O(1)
A ‘for’ loop dictated by a loop index that goes up to n –
O(n)
A nested ‘for’ loop with outer controlled by n and inner
controlled by m – O(mn)
Loop with a range of values n, where each iteration
reduces the range by a fixed constant fraction(e.g.: ½) –
O(logn)
For a recursive method: each call is usually O(1). Thus,
If n calls are made – O(n)
If n log n calls are made – O(n log n)
58
