Scribd
Upload
9 views

Algorithm Ch 1 Lec 2

The document discusses the analysis of algorithms, focusing on running time and memory management, and introduces asymptotic analysis, which measures algorithm efficiency independent of machine type or implementation. It explains three main asymptotic notations: Big O (upper bound), Big Omega (lower bound), and Theta (tight bound), providing definitions and examples for each. Additionally, it covers randomized algorithms, differentiating between Las Vegas and Monte Carlo types, and their applications in decision-making processes.

Uploaded by

Safwan Samad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views

Algorithm Ch 1 Lec 2

The document discusses the analysis of algorithms, focusing on running time and memory management, and introduces asymptotic analysis, which measures algorithm efficiency independent of machine type or implementation. It explains three main asymptotic notations: Big O (upper bound), Big Omega (lower bound), and Theta (tight bound), providing definitions and examples for each. Additionally, it covers randomized algorithms, differentiating between Las Vegas and Monte Carlo types, and their applications in decision-making processes.

Uploaded by

Safwan Samad
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 26

Analysis of an Algorithm

 The goal of analysis of an algorithm is to compare


algorithm in running time and also Memory
management.
 Running time of an algorithm depends on how long it
takes a computer to run the lines of code of the
algorithm.
Running time of an algorithm depends on
1.Speed of computer
2.Programming language
3.Compiler and translator
ASYMPTOTIC ANALYSIS:
 Expressing the complexity in term of its relationship
to known functions. This type analysis is called
asymptotic analysis.
The main idea of Asymptotic analysis is to have a
measure of efficiency of an algorithm, that doesn’t
depends on
1. Type of machine.
2.Doesn’t require algorithm to be implemented.
3.Time taken to write the program.
ASYMPTOTIC NOTATION

ASYMPTOTIC NOTATION: The mathematical way of


representing the Time complexity.
The notation 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.

Definition : It is the way to describe the behavior of functions.


Asymptotic growth: The rate at which the function grows…
“growth rate” is the complexity of the function or the amount of
resource it takes up to compute.

Growth rate Time +memory


Classification of growth
1. Growing with the same rate.
2. Growing with the slower rate.
3. Growing with the faster rate.
They are 3 asymptotic notations are mostly used to
represent time complexity of algorithm.

1. Big oh (O)notation
2. Big omega (Ω) notation
3. Theta(Θ) notation
1.Big oh (O)notation
1. Big oh (O)notation : Asymptotic “less than”(slower rate).This
notation mainly represent upper bound of algorithm run time.
Big oh (O)notation is useful to calculate maximum amount of time of
execution.
By using Big-oh notation we have to calculate worst case time complexity.
Formula : f(n)<=c g(n) n>=n0 , c>0 ,n0 >=1
Definition: Let f(n) ,g(n) be two non negative (positive) function. The
function f(n)=O(g(n)) if and only if there exist two positive constant c, n0
such that f(n)<= c. g(n) for all value of n > 0 & c>0
 We use O-notation to give an asymptotic upper bound of a function, to
within a constant factor.
 means that there existes some constant c s.t. is
always for large enough n.
Examples
Example : f(n)=3n +2 & g(n)= n
Formula : f(n)<=c g(n) n>=n0 , c>0 ,n0 >=1
Now 3n+2 <= c.n
3n+2 <= 4.n
Put the value of n =1
5<=4 false
n = 2 8<=8 true
Now 3n+2<=4n is true for all values of n >=2 and c=4
Therfore , f(n)<= c.g(n)
Above condition is satisfied . And this notation takes maximum amount of time
to execute . So that it is called worst case complexity.
Examples

8/31/2024
Theorem

8/31/2024
2.Ω-Omega notation
Ω-Omega notation : It represent Lower bound of algorithm run
time.

By using Big Omega notation we can calculate minimum amount of


time. We can say that it is best case time complexity.

Formula : f(n)>=c g(n) n>=n0 , c>0 ,n0 >=1


where c is constant, n is function variable.
Ω-Omega notation

 We use Ω-notation to give an asymptotic lower bound on


a function, to within a constant factor.
 f (n)  ( g(n)) means that there exists some constant c s.t.
f (n) is always  cg (n) for large enough n.
Examples
Example : f(n)=3n +2 and g(n) = n
Formula : f(n)>=c g(n) n>=n0 , c>0 ,n0 >=1
f(n)=3n+2
3n+2>=1*n, c=1
Now putting the value of n=1, 5>=1 true
It means that f(n)= Ω g(n).
More Examples

8/31/2024
3. -Theta notation
Theta (Θ) notation : Asymptotic “Equality”(same rate).
It represent average bond of algorithm running time.

By using theta notation we can calculate average amount of time. So it


called average case time complexity of algorithm.
Formula : c1 g(n)<= f(n)<= c2 g(n)
where c is constant, n is function variable
Θ -Theta notation
 A function f (n) belongs to the set ( g (n)) if there exist
positive constants c1 and c2 such that it can be “sand-
wiched” between c1g (n) and c2 g (n) for sufficienly large
n.

 f (n)  ( g (n)) means that there exists some constant c1


and c2 s.t. c1 g (n)  f (n)  c2 g (n) for large enough n.
Examples
Example : Let f(n)=3n+2 and g(n) = n
Formula : c1 g(n)<=f(n)<=c2 g(n)
f(n)=3n+2
1*n<=3n+2<=4*n now put the value of
n=1 we get 1<=5<=4 false
n=2 we get 2<=8<=8 true
n=3 we get 3<=11<=12 true
Now all value of n>=2 it is true above condition is satisfied.
Therfore. 3n +2 = Θ(n)
More Examples

8/31/2024
Example of asymptotic notation

Problem:-Find upper bond ,lower bond & tight bond range for
functions: f(n)= 2n+5
Solution:-Let us given that f(n)= 2n+5 , now g(n)= n
lower bond=2n, upper bond =3n, tight bond=2n
1. For Big –oh notation(O):- according to definition
f(n)<=cg(n) for Big oh we use upper bond so
f(n)=2n+5, g(n)=n and c=3 according to definition
2n+5<=3n
Put n=1 7<=3 false Put n=2 9<=6 false Put n=3 14<=9 false
Put n=4 13<=12 false Put n=5 15<=15 true
now for all value of n>=5 above condition is satisfied. C=3 n>=5
2. Big - omega notation :- f(n)>=c.g(n) we know that this
Notation is lower bond notation so c=2
Let f(n)=2n+5 & g(n)=n
Now 2n+5>=c.g(n);
2n+5>=2n put n=1
We get 7>=2 true for all value of n>=1,c=2 condition is satisfied.

3. Theta notation :- according to definition


c1.g(n)<=f(n)<=c2.g
RANDOMIZED ALGORITHMS
 A randomized algorithm is an algorithm that makes use of a randomizer (such as
random number generator). Some of the decisions made in the algorithm depend
on the output of the randomizer.

 Since the output of any randomizer might differ in an unpredictable way from run
to run, the output of a randomized algorithm could also differ from run to run for
the same input.

 The algorithm typically uses uniformly random bits as an auxiliary input to guide
its behavior, in the hope of achieving good performance in the "average case" over
all possible choices of random bits.

 An algorithm that uses random numbers to decide what to do next anywhere in its
logic is called Randomized Algorithm..

 Example: Quick sort


Randomized Algorithm (Cont.)
 Two classes of Randomized algorithms
1. Las Vegas algorithms: This algorithm produce
the same (correct) output for the same input. The
execution time of a Las vegas algorithm depends on the
output of the randomizer.
2. Monte Carlo algorithm: The outputs of this type
of algorithms might differ from run to run.

8/31/2024
Monte Carlo Algorithm (Cont.)
Example : Problems where there are only two possible
answers: Yes and No. If a Monte Carlo algorithm is
employed to solve such a problem, then the algorithm
might give incorrect answers depending on the output of
the randomizer. We require that the probability of an
incorrect answer from a Monte Carlo algorithm be low.

* Typically for a fixed input a Monte Carlo algorithm


does not display much variation in execution time
between runs, whereas in the case of Las Vegas
algorithm this variation is significant.
8/31/2024
Randomized Algorithm (Cont.)
 One simple example of a Monte Carlo algorithm is to
calculate the probability of rolling two standard dice.
There are 36 combinations of dice rolls.
 You can decide an event to occur (Yes or No)
depending on the outcome of particular face pattern
of the two dices.

8/31/2024

You might also like