Lecture 05
Analysis of algorithms
CSE225: Data Structures and Algorithms
Definition
• An algorithm is a finite set of precise instructions for
performing a computation or for solving a problem.
• It must produce the correct result
• It must finish in some finite time
•You can represent an algorithm using
• pseudocode,
• flowchart, or
• even actual code
Algorithm Description : pseudocode vs flowchart
Next we will illustrate how the problem of sorting numbers can be solved using insertion-sort
algorithm (represented using the pseudocode convention of Cormen et al.)
Analysis of Algorithms
• What does it mean to analyze an algorithm?
• To have an estimate about how much time an algorithm may take to
finish, or in other words, to analyze its running time (aka. Time
complexity)
• Sometimes, instead of running time, we are interested in how much
memory/space the algorithm may consume while it runs (space
complexity)
•It enables us to compare between two algorithms
• What do we mean by running time analysis?
• Also referred to as time-complexity analysis
• To determine how running time increases as the size of the problem
increases.
Analysis of Algorithms
• Size of the problem can be a range of things, including
• size of an array
• polynomial degree of an equation
• number of elements in a matrix
• number of bits in the binary representation of the input
.
and so on…
How Do We Analyze Running Time?
We need to define an objective measure.
(1) Compare execution times?
Not good: time is specific to a particular computer, operating system, etc !!
How Do We Analyze Running Time?
We need to define an objective measure.
(2) Count the number of statements executed?
Associate a "cost" with each statement.
Find the "total cost“ by finding the total number of times each statement
is executed.
Not good: number of statements vary with the programming language as
well as the style of the individual programmer.
Algorithm 1 Algorithm 2
Time (micro sec) c1 c2 c3 Time (micro sec)
arr[0] = 0; c1 for(i=0; i<N; i++) c1+c2(N+1)+ c3N
arr[1] = 0; c1 arr[i] = 0; c1N
arr[2] = 0; c1 -----------------------------
... g(n)= c1+c2(N+1)+c3N+c1N = (c1+c2+c3)N+(c1+c2)
arr[N-1] = 0; c1
----------------------
f(n)= c1+c1+...+c1 = c1N
Observation: For very large values of N, execution time of both programs is similar. Thus we can
say that both of them have roughly the same running time.
Ideal Solution to Express runtime in theory
Express runtime as a function of the input size n (i.e., f(n)) in order to understand
how f(n) grows with n
and count only the most significant term of f(n) and ignore everything else (because
those won’t affect running time much for very large values of n).
Thus the running times (called time complexity) of the programs of previous slide
becomes:
f(N)= c1N ≈ N*(some constant)
g(N) = (c1+c2+c3)N+(c1+c2) ≈ N*(some constant)
Thus both these functions grows linearly with N and as such both have the same
running time (specifically, linear running time). We say that both of them are O(N)
functions, which means that, the running time of each of these algorithms is a
constant multiple of N (we ignore the value of the constant).
We compare running times of different functions in an asymptotic manner (i.e., we
check if f(n) is > g(n) for very large values of n).
Advantage of Time Complexity
The notion of time complexity is independent of machine type, operating
system, programming style, etc. As a result, we can easily compare the
performance of two algorithms without thinking about the platform used to
implement those algorithms.
Note:
Actual execution time is also important because sometimes we see that one
algorithm has lower time complexity but in practice, it performs worse. This
may happen, for e.g., in the following case:
Algorithm A has time complexity f(n)= cn and
Algorithm B has time complexity g(n) = dn 2
So theoretically, algorithm A is better (takes less time) than B. But it turns
out that B takes less time than A for real inputs. This may happen because
• n is not large practice and
• c >> d
Asymptotic Analysis (more examples)
• Consider the example of buying elephants and goldfish:
Cost: cost_of_elephants + cost_of_goldfish
Cost ~ cost_of_elephants (approximation)
• The low order terms, as well as constants in a function are
relatively insignificant for large n
• f(n) = 6n + 4 ≈ (some constant) n
• g(n) = n4 + 100n2 + 10n + 50 ≈ (some constant) n4
i.e., we say that n4 + 100n2 + 10n + 50 and n4 have the
same rate of growth. However, f(n) and g(n) have
different rate of growths.
Which one grows faster for large values of n?
Big-O Notation
We say is in the order of , or
Growth rate of is constant, that is, it is not dependent on
problem size. → Constant time
is in the order of , or
Growth rate→ofLinear
is roughly
time proportional to the growth rate of .
is in the order of , or
Growth rate of is roughly proportional to the growth rate of .
→ Quadratic time
In general, any function is faster- growing than any
function.
For large , a algorithm runs a lot slower than a algorithm.
• O(2n), O(4n), etc. are called exponential time
Visualizing Orders of Growth
• On a graph, as you go to the right, a faster growing
function eventually becomes larger.
fA(n)=30n+8
Running time
fB(n)=n2+1
Increasing n
Growth of Functions
Complexity Graphs
log(n)
Complexity Graphs
n log(n)
log(n)
Complexity Graphs
n10 n3
n2
n log(n)
Complexity Graphs (log scale)
3n
nn
n20
2n
n10
1.1n
Asymptotic Notations
O-notation
O(g(n)) is the set of functions
with smaller or same order of
growth as g(n)
Examples:
T(n) = 3n2+10nlgn+8 is O(n2), O(n2lgn), O(n3), O(n4), …
T’(n) = 52n2+3n2lgn+8 is O(n2lgn), O(n3), O(n4), …
Loose upper
bounds
Proving Asymptotic Upper Bound
Show that T(n) = 3n2+10nlgn+8 is O(n2).
For n > 1 (because for n < 1, n2 < 1) we have:
3n2+10nlgn+8 3n2+10n2+8n2
Þ3n2+10nlgn+8 21n2
Therefore, for c = 21 and n0 = 1:
T(n) cn2 whenever n > n0.
T(n) is O(n2).
Proving Asymptotic Upper Bound
Show that T(n) = 3n2+10nlgn+8 is O(n2 lg n).
For n > 2 (because for n < 2, lg n < 1, so it is possible that
n2lg n < n lg n which is true when n = 1.5) we have:
3n2+10nlgn+8 3n2(lg n)+10n2(lg n)+8n2(lg n)
Þ3n2+10nlgn+8 21n2(lg n)
Therefore, for c = 21 and n0 = 2:
T(n) cn2lgn whenever n > n0.
T(n) is O(n2lgn).
Proving Asymptotic Upper Bound
Show that T’(n) = 52n2+3n2lgn+8 is O(n2 lg n).
For n > 2 (because for n < 2, lg n < 1, so it is possible that
n2lg n < n2 which is true when n < 2) we have:
52n2+3n2lgn+8 52n2(lg n)+3n2(lg n)+8n2(lg n)
Þ52n2+3n2lgn+8 63n2(lg n)
Therefore, for c = 63 and n0 = 2:
T’(n) cn2lgn whenever n > n0.
T(n) is O(n2lgn).
Proving Asymptotic Upper Bound
Show that f(n) = 5n2+3n2lgn-8 is O(n2 lg n).
(do yourself)
Big-O Visualization
Some Examples
Determine the time complexity for the following algorithm.
count = 0;
for(i=0; i<10000; i++)
count++;
We always want to know the tight upper
bound; not some loose upper bounds
Some Examples
Determine the time complexity for the following algorithm.
count = 0;
for(i=0; i<10000; i++)
O(1)
count++;
Some Examples
Determine the time complexity for the following algorithm.
count = 0;
for(i=0; i<n; i++)
count++;
Some Examples
Determine the time complexity for the following algorithm.
count = 0;
for(i=0; i<n; i++)
O(n)
count++;
Some Examples
Determine the time complexity for the following algorithm.
sum = 0;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
sum += arr[i][j];
Some Examples
Determine the time complexity for the following algorithm.
sum = 0;
for(i=0; i<n; i++)
for(j=0; j<n; j++) O(n2)
sum += arr[i][j];
Does implementation matter?
Determine the time complexity for the following algorithm.
char someString[10];
gets(someString);
for(i=0; i<strlen(someString); i++)
someString[i] -= 32;
Does implementation matter?
Determine the time complexity for the following algorithm.
char someString[10];
gets(someString); O(n 2
)
for(i=0; i<strlen(someString); i++)
someString[i] -= 32;
Does implementation matter?
char someString[10];
gets(someString); O(n2)
for(i=0; i<strlen(someString); i++)
someString[i] -= 32;
Can we re-implement it to make it more efficient? YES
char someString[10];
gets(someString); O(n)
int t = strlen(someString);
for(i=0; i<t; i++)
someString[i] -= 32;
This example shows that a badly implemented algorithm may have
greater time complexity than a more efficient implementation
