Lecture2 M 131122062242 Phpapp02

Algorithms
1
Informally Definition
An algorithm is any well-defined

computational procedure that
takes some values or set of
values as input and produces
some values or set of values as
output
Formal Definition
As a sequence of computational
steps that transforms the input
into output
Algorithms
Properties of algorithms:
• Input from a specified set,

• Output from a specified set (solution),
• Definiteness of every step in the computation,
• Correctness of output for every possible input,
• Finiteness of the number of calculation steps,
• Effectiveness of each calculation step and
• Generality for a class of problems.
4
?
Suppose computers were infinitely fast and
computer memory are free
Is there any reason to study algorithm ?
Yes
– Demonstrate that solution methods
terminates and does so with correct
answer.
If computers were infinitely fast,
any correct method for solving a
problem would do.
You would probably want your

implementation to be within the
bounds of good software
engineering practice
In reality
Computers may be fast, but they
are not infinitely fast and
Memory may be cheap but it is not
free
Computing time is therefore a

bounded resource and so is the
space in memory
Complexity
In general, we are not so much interested

in the time and space complexity for small
inputs.
For example, while the difference in time

complexity between linear and binary
search is meaningless for a sequence with n
= 10, it is gigantic for n = 230.
8
Complexity
For example, let us assume two algorithms A and

B that solve the same class of problems.
The time complexity of A is 5,000n, the one for
B is 1.1n for an input with n elements.
For n = 10, A requires 50,000 steps, but B only
3, so B seems to be superior to A.
For n = 1000, however, A requires 5,000,000
steps, while B requires 2.51041 steps.
9
Complexity
Comparison: time complexity of algorithms A and B
Input Size Algorithm A Algorithm B

n 5,000n 1.1n
10 50,000 3
100 500,000 13,781
1,000 5,000,000 2.51041
1,000,000 5109 4.81041392
10
Complexity
This means that algorithm B cannot be used for

large inputs, while algorithm A is still feasible.
So what is important is the growth of the

complexity functions.
The growth of time and space complexity with

increasing input size n is a suitable measure for
the comparison of algorithms.
11
Growth Function
The order of growth / rate of growth

of the running time of an algorithm
gives a simple characterization of the
algorithm efficiency and allow us to
compare the relative performance of
alternative algorithm
12
Asymptotic Efficiency
Algorithm
When the input size is large enough so
that the rate of growth / order of
growth of the running time is relevant
That is we are concerned with how the

running time of an algorithm
increases with the size of the input in
the limit, as the size of the input
increases without bound
13
Asymptotic Efficiency
Algorithm
Usually, an algorithm that is

asymptotically more efficient will
be the best choice for all but
very small inputs.
14
Asymptotic Notation
The notations we use to describe

the asymptotic running time of an
algorithm are defined in terms of
functions whose domains are the
set of natural numbers N = {0, 1,
2,…. }
15
Asymptotic Notation
Asymptotic notations are

convenient for describing the
worst-case running time function
T(n), which is defined only on
integer input size.
16
Asymptotic Notation
Let n be a non-negative integer

representing the size of the input
to an algorithm
17
Asymptotic Notation
Let f(n) and g(n) be two positive
functions, representing the
number of basic calculations
(operations, instructions) that an
algorithm takes (or the number
of memory words an algorithm
needs).
18
Asymptotic Notation
Q - Big Theta
O – Big O
W - Big Omega
o – Small o
w - Small Omega
19
 - Notation
For a given function g(n), we denote
by (g(n)) the set of functions
(g(n)) = {f(n) : there exist

positive constants c1 , c2 , and
n0 such that 0  c1 g(n)  f(n) 
c2 g(n) for all n  n0
f(n)  (g(n)) f(n) = (g(n))
20
 - Notation
g(n) is an
asymptotically tight
bound for f(n).
f(n) and g(n) are

nonnegative, for large
n.
21
Example
(g(n)) = {f(n) :  positive constants c1, c2,
and n0, such that n  n0, 0  c1g(n)
 f(n)  c2g(n) }
1/2n2 - 3n = Q(n2)
Determine the positive constant n0,
c1, and c2 such that
c1 n2  1/2n2 - 3n  c2 n2 n  n0
22
Example Contd ...
c1  1/2 – 3/n  c2 (Divide by n2)
c1 = 1/14 , c2 = ½ , n0 = 7
1/2n2 - 3n = Q(n2)
23
O-Notation
For a given function g(n)
O(g(n)) = {f(n) : there exist
positive constants c and n0 such
that 0  f(n)  c g(n) for all n 
n0 }
Intuitively: Set of all functions whose rate of
growth is the same as or lower than that of
c. g(n)
24
O-Notation
g(n) is an asymptotic upper bound for f(n).

f(n) = (g(n))  f(n) = O(g(n)).
(g(n))  O(g(n)). 25
Example
O(g(n)) = {f(n) : there exist positive
constants c and n0 such that 0  f(n) 
c g(n) for all n  n0 }
Any linear function an + b is in

O(n2). How?
C = a + |b| and n0 = 1
26
Big-O Notation
(Examples)
f(n) = 5n+2 = O(n) // g(n) = n
– f(n)  6n, for n  3 (C=6, n0=3)
f(n)=n/2 –3 = O(n)
– f(n)  0.5 n for n  0 (C=0.5, n0=0)
n2-n = O(n2) // g(n) = n2
– n2-n  n2 for n  0 (C=1, n0=0)
n(n+1)/2 = O(n2)
– n(n+1)/2  n2 for n  0 (C=1, n0=0)
27
 - Notation
For a given function g(n)
(g(n)) = {f(n) : there exist
positive constants c and n0 such
that 0  c g(n)  f(n) for all
n  n0 }
Intuitively: Set of all functions whose
rate of growth is the same as or higher
than that of g(n).
28
 - Notation
g(n) is an asymptotic lower bound for f(n).

f(n) = (g(n))  f(n) = (g(n)).
(g(n))  (g(n)). 29
Relations Between Q, O, W
30
Relations Between Q, O, W
For any two function f(n) and g(n),
we have f(n) = (g(n)) if and only
if f(n) = O(g(n)) and f(n) =
(g(n))
That is
(g(n)) = O(g(n)) Ç W(g(n))
31
The Growth of Functions
“Popular” functions g(n) are
n log n, 1, 2n, n2, n!, n, n3, log n
Listed from slowest to fastest growth:

• 1
• log n
• n
• n log n
• n2
• n3
• 2n
• n!
32
Comparing Growth Rates
2n n2
n log2 n
T(n)
log2 n
Problem Size
Example: Find sum of array elements
Algorithm arraySum (A, n)
Input array A of n integers
Output Sum of elements of A # operations
sum  0
1
for i  0 to n  1 do n+1
sum  sum + A [i] n
return sum 1
Input size: n (number of array elements)
Total number of steps: 2n + 3
Example: Find max element of an
array
Algorithm arrayMax(A, n)
Input array A of n integers
Output maximum element of A #
operations
currentMax  A[0]
1
for i  1 to n  1 do
n
if A [i]  currentMax then
n -1
 Input size: n (number of array elements)
currentMax  A [i]
 Total number of steps: 3n
n -1
return currentMax

Lecture2 M 131122062242 Phpapp02

Uploaded by

Copyright:

Available Formats

Lecture2 M 131122062242 Phpapp02

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture2 M 131122062242 Phpapp02

Uploaded by

Copyright:

Available Formats

Algorithms

An algorithm is any well-defined

• Input from a specified set,

Is there any reason to study algorithm ?

You would probably want your

Computing time is therefore a

In general, we are not so much interested

For example, while the difference in time

For example, let us assume two algorithms A and

Input Size Algorithm A Algorithm B

This means that algorithm B cannot be used for

So what is important is the growth of the

The growth of time and space complexity with

The order of growth / rate of growth

That is we are concerned with how the

Usually, an algorithm that is

The notations we use to describe

Asymptotic notations are

Let n be a non-negative integer

(g(n)) = {f(n) : there exist

f(n) and g(n) are

c1  1/2 – 3/n  c2 (Divide by n2)

g(n) is an asymptotic upper bound for f(n).

Any linear function an + b is in

g(n) is an asymptotic lower bound for f(n).

Listed from slowest to fastest growth:

You might also like