introduction to algorithm for beginneer1

algorithm concepts

1. 11-May-24 Algo Analysis 1
Topics
Analysis of Algorithms
Asymptotic Notations
Examples

2. 11-May-24 Algo Analysis 2
Algorithm
An algorithm is a well defined
computational procedure that takes
some value, or set of values, as input
and produces some value, or set of
values, as output.
In other words an algorithm is a
sequence of computational steps that
transform the input into the output.

3. 11-May-24 Algo Analysis 3
Motivation to Analyze Algorithms
Understanding the resource requirements of an
algorithm
Time
Space
Running time analysis estimates the time
required of an algorithm as a function of the
input size.
Usages:
Estimate growth rate as input grows.
Allows to choose between alternative algorithms.

4. 11-May-24 Algo Analysis 4
Three Running Times for an Algorithm
Best Case: When the situation is ideal.
For e.g. : Already sorted input for a
sorting algorithm. Not an interesting case
to study. Lower bound on running time
Worst case: When situation is worst. For
e.g.: Reverse sorted input for a sorting
algorithm. Interesting to study since then
we can say that no matter what the input
is, algorithm will never take any longer.
Upper bound on running time for any
input.

5. 11-May-24 Algo Analysis 5
Three Running Times for an Algorithm
Average case: Any
random input. Often
roughly as bad as worst
case. Problem with this
case is that it may not
be apparent what
constitutes an “average”
input for a particular
problem.0
20
40
60
80
100
120
Running Time
1000 2000 3000 4000
Input Size
best case
average case
worst case

6. 11-May-24 Algo Analysis 6
Experimental Studies
Write a program
implementing the
algorithm
Run the program with
inputs of varying size and
composition
Use a method like
System.currentTimeMillis()to
get an accurate measure
of the actual running
time
Plot the results0
1000
2000
3000
4000
5000
6000
7000
8000
9000
0 50 100
Input Size
Time (ms)

7. 11-May-24 Algo Analysis 7
Limitations of Experiments
It is necessary to implement the
algorithm, which may be difficult
Results may not be indicative of the
running time on other inputs not
included in the experiment.
In order to compare two algorithms, the
same hardware and software
environments must be used

8. 11-May-24 Algo Analysis 8
Theoretical Analysis
Uses a high-level description of the
algorithm instead of an implementation
Characterizes running time as a function
of the input size, n.
Takes into account all possible inputs
Allows us to evaluate the speed of an
algorithm independent of the
hardware/software environment

9. 11-May-24 Algo Analysis 9
Analysis and measurements
Performance measurement (execution
time): machine dependent.
Performance analysis: machine
independent.
How do we analyze a program
independent of a machine?
Counting the number steps.

10. 11-May-24 Algo Analysis 10
RAM Model of Computation
In RAM model of computation instructions are
executed one after another.
Assumption: Basic operations (steps) take 1
time unit.
What are basic operations?
Arithmetic operations, comparisons, assignments,
etc.
Library routines such as sortshould not be
considered basic.
Use common sense

11. 11-May-24 Algo Analysis 11
Pseudo code
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
By inspecting the pseudo code, we can
determine the maximum number of
primitive operations executed by an
algorithm, as a function of the input size.

12. 11-May-24 Algo Analysis 12
Example 1:
Input size: n (number of array elements)
Total number of steps: 2n + 3
AlgorithmarraySum (A, n)
Inputarray Aof nintegers
OutputSum of elements of A # operations
sum0 1
fori0ton1do n+1
sumsum + A [i] n
returnsum 1
Example: Find sum of array elements

13. 11-May-24 Algo Analysis 13
Example 2
AlgorithmarrayMax(A, n)
Inputarray Aof nintegers
Outputmaximum element of A # operations
currentMaxA[0] 1
fori1ton1do n
ifA [i] currentMaxthen n -1
currentMaxA [i] n -1
returncurrentMax 1
Example: Find max element of an
array
Input size: n (number of array elements)
Total number of steps: 3n

14. 11-May-24 Algo Analysis 14
Seven Growth Functions
Seven functions that often appear in
algorithm analysis:
Constant 1
Logarithmic log n
Linear n
Log Linear n log n
Quadratic n
2
Cubic n
3
Exponential 2
n

15. 11-May-24 Algo Analysis 15
The Constant Function
f(n) = c for some fixed constant c.
The growth rate is independent of the input
size.
Most fundamental constant function is g(n) =
1
f(n) = c can be written as
f(n) = cg(n)
Characterizes the number of steps needed to
do a basic operation on a computer.

16. 11-May-24 Algo Analysis 16
The Linear and Quadratic Functions
Linear Function
f(n) = n
For example comparing a number x to
each element of an array of size n will
require n comparisons.
Quadratic Function
f(n) = n
2
Appears when there are nested loops in
algorithms

17. 11-May-24 Algo Analysis 17
Example 3
Total number of steps: 2n
2
+ 2n + 2
AlgorithmMystery(n) # operations
sum 0 1
fori0ton1do n + 1
forj0ton1do n (n + 1)
sum sum + 1 n .n

18. 11-May-24 Algo Analysis 18
The Cubic functions and other polynomials
Cubic functions
f(n) = n
3
Polynomials
f(n) = a
0 + a
1n+ a
2n
2
+ …….+a
dn
d
d is the degree of the polynomial
a
0,a
1….... a
d are called coefficients.

19. 11-May-24 Algo Analysis 19
The Exponential Function
f(n) = b
n
b is the base
n is the exponent
For example if we have a loop that starts by
performing one operation and then doubles
the number of operations performed in the
nth iteration is 2
n .
Exponent rules:
(b
a
)
c
= b
ac
b
a
b
c
= b
a+c
b
a
/b
c
= b
a-c

20. 11-May-24 Algo Analysis 20
The Logarithm Function
f(n) = log
bn
b is the base
x = log
bn if and only if b
x
= n
Logarithm Rules
log
bac = log
ba + log
bc
Log
ba/c = log
ba –log
bc
log
ba
c
= clog
ba
log
ba = (log
da)/ log
db
b
log d a
= a
log d b

21. 11-May-24 Algo Analysis 21
The N-Log-N Function
f(n) = nlogn
Function grows little faster than linear
function and a lot slower than the
quadratic function.

22. 11-May-24 Algo Analysis 22
Growth rates Compared
n=1n=2n=4n=8n=16n=32
1 1 1 1 1 1 1
logn 0 1 2 3 4 5
n 1 2 4 8 16 32
nlogn0 2 8 2464 160
n
2
1 4 1664256 1024
n
3
1 8 64512409632768
2
n
2 4 16235655364294967296

23. 11-May-24 Algo Analysis 23
Asymptotic Notation
Although we can sometimes determine
the exact running time of an algorithm,
the extra precision is not usually worth
the effort of computing it.
For large enough inputs, the
multiplicative constants and lower order
terms of an exact running time are
dominated by the effects of the input
size itself.

24. 11-May-24 Algo Analysis 24
Asymptotic Notation
When we look at input sizes large
enough to make only the order of
growth of the running time relevant we
are studying the asymptotic efficiency
of algorithms.
Three notations
Big-Oh (O) notation
Big-Omega(Ω) notation
Big-Theta(Θ) notation

25. 11-May-24 Algo Analysis 25
Big-Oh Notation
A standard for expressing upper bounds
Definition: f(n) = O (g(n)) if there exist constant
c > 0 and n
0>=1 such that f(n) ≤ cgn) for all n≥ n
0
We say: f(n)is big-O of g(n), or
The time complexity off(n) isg(n).
Intuitively, an algorithm A is O(g(n)) means that,
if the input is of size n, the algorithm will stop
after g(n) time.
The running time of Example 1 is O(n), i.e., ignore
constant 2 and value 3 (f(n)= 2n + 3).
because f(n) ≤ 3nfor n≥ 10 (c= 3, and n
0= 10)

26. 11-May-24 Algo Analysis 26
Example 4
Definition does not require upper bound to be
tight, though we would prefer as tight as possible
What is Big-Oh of f(n) = 3n+3
Let g(n) = n, c = 6 and n
0= 1;
f(n) = O(g(n)) = O(n) because 3n+3 ≤ 6g(n) if n ≥ 1
Let g(n) = n, c = 4 and n
0= 3;
f(n) = O(g(n)) = O(n) because 3n+3 ≤ 4g(n) if n ≥ 3
Let g(n) = n
2
, c = 1 and n
0= 5;
f(n) = O(g(n)) = O(n
2
) because 3n+3 ≤ (g(n))
2
if n≥
5
We certainly prefer O(n).

27. 11-May-24 Algo Analysis 27
Example 5
What is Big-Oh for f(n) = n
2
+ 5n –3?
Let g(n) = n
2
, c = 2and n
0= 6.
Then f(n) = O(g(n)) = O(n
2
)because
f(n) ≤2 g(n)if n ≥n
0.
i.e., n
2
+ 5n –3 ≤2n
2
ifn ≥6

28. 11-May-24 Algo Analysis 28
More about Big-Oh notation
Asymptotic: Big-Oh is meaningful only
when n is sufficiently large
n ≥n
0 means that we only care about
large size problems.
Growth rate: A program with O(g(n)) is
said to have growth rate of g(n). It
shows how fast the running time grows
when n increases.

29. 11-May-24 Algo Analysis 29
More nested loops
1int k = 0;
2for (i=0; i<n; i++)
3 for (j=i; j<n; j++)
4 k++;
Running time)(2/)1()(
2
1
0
nOnnin
n
i




30. 11-May-24 Algo Analysis 30
Big-Omega Notation
A standard for expressing lower bounds
Definition (omega): f(n) = Ω(g(n))
if there exist some constants c >0 and
n
0>= 1 such that f(n) ≥ cg(n) for all n
≥ n
0

31. 11-May-24 Algo Analysis 31
Big-Theta Notation
A standard for expressing exact bounds
Definition (Theta): f(n) = Θ(g(n)) if and
only if f(n) =O(g(n)) and f(n) = Ω(g(n)).
An algorithm is Θ(g(n)) means that g(n) is
a tight bound (as good as possible) on its
running time.
On all inputs of size n, time is ≤ g(n)
On all inputs of size n, time is ≥ g(n)

32. 11-May-24 Algo Analysis 32
Computing Fibonacci numbers
We write the following program: a
recursive program
1 long int fib(n) {
2if (n <= 1)
3 return 1;
4else return fib(n-1) + fib(n-2)
Let us analyze the running time.

33. 11-May-24 Algo Analysis 33
fib(n) runs in exponential time
Let T denote the running time.
T(0) = T(1) = c
T(n) = T(n-1) + T(n-2) + 2
where 2 accounts for line 2 plus the
addition at line 3.
It can be shown that the running time
is Ω((3/2)
n
).
So the running time grows
exponentially.

34. 11-May-24 Algo Analysis 34
Efficient Fibonacci numbers
Avoid recomputation
Solution with linear running time
int fib(int n) {
int fibn=0, fibn1=0, fibn2=1;
if (n < 2)
return n
else {
for( int i = 2; i <= n; i++ ) {
fibn = fibn1 + fibn2;
fibn1 = fibn2;
fibn2 = fibn;
}
return fibn;
}}

35. 11-May-24 Algo Analysis 35
Summary: lower vs. upper bounds
This section gives some ideas on how to analyze
the complexity of programs.
We have focused on worst case analysis.
Upper bound O(g(n)) means that for sufficiently
large inputs, running time f(n) is bounded by a
multiple of g(n).
Lower bound Ω(g(n)) means that for sufficiently
large n, there is at least one input of size n such
that running time is at least a fraction of g(n)
We also touch the “exact” bound Θ(g(n)).

36. 11-May-24 Algo Analysis 36
Summary: algorithms vs. Problems
Running time analysis establishes
bounds for individual algorithms.
Upper bound O(g(n)) for a problem:
there is some O(g(n)) algorithms to
solve the problem.
Lower bound Ω(g(n)) for a problem:
every algorithm to solve the problem is
Ω(g(n)).