Scribd
Upload
42 views6 pages

Analysis of Algorithms

The document discusses the analysis of algorithms, focusing on the efficiency measurement through asymptotic notations: Big-O, Omega, and Theta. Big-O notation indicates the upper bound or worst-case complexity, Omega notation represents the lower bound or best-case complexity, and Theta notation provides both bounds for average-case complexity. Examples are provided for each notation to illustrate their application in analyzing algorithm performance.

Uploaded by

krishnasneha98
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
42 views6 pages

Analysis of Algorithms

The document discusses the analysis of algorithms, focusing on the efficiency measurement through asymptotic notations: Big-O, Omega, and Theta. Big-O notation indicates the upper bound or worst-case complexity, Omega notation represents the lower bound or best-case complexity, and Theta notation provides both bounds for average-case complexity. Examples are provided for each notation to illustrate their application in analyzing algorithm performance.

Uploaded by

krishnasneha98
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/ 6

Analysis of Algorithms

 The main idea of analysis of algorithms is to have a


measure of the efficiency of algorithms.
 Asymptotic notations are mathematical tools to
represent the time complexity of algorithms for
analysis of algorithms.
Types of Asymptotic Notations in
Complexity Analysis of Algorithms:
I. Big-O Notation (O-notation)
II. Omega Notation (Ω-notation)
III. Theta Notation (Θ-notation)

1.Big-O Notation (O-notation):


 Big-O notation represents the upper bound of the
running time of an algorithm. Therefore, it gives the
worst-case complexity of an algorithm.
 It is the most widely used notation for Asymptotic
analysis.
 It specifies the upper bound of a function and the
maximum time required by an algorithm or the
worst-case time complexity.

ER-DSP-Analysis of Algorithms Page 1


If f(n) describes the running time of an algorithm, f(n)
is O(g(n)) if there exist a positive constant C and n0
such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
n0.

Examples:
1. 3n+2= O(n) as 3n+2<=4n for all n>=2
2. 3n+3= O(n) as 3n+3<=4n for all n>=3
3. 100n+6= O(n) as 100n+6<=101n for all n>=6
4. 10n2 + 4n+2 = O(n2) as 10n2 + 4n+2 <=11n2for all n>=5
5. 6*2n + n2 = O(2n) as 6*2n + n2<=7*2n for n>=4
ER-DSP-Analysis of Algorithms Page 2
2.Omega Notation (Ω-Notation):
 Omega notation represents the lower bound of the
running time of an algorithm. Thus, it provides the
best case complexity of an algorithm.
 The execution time serves as a lower bound on the
algorithm’s time complexity.
 It is defined as the condition that allows an
algorithm to complete statement execution in the
shortest amount of time.

Let g and f be the function from the set of natural


numbers to itself. The function f is said to be Ω(g), if
there is a constant c > 0 and a natural number n0 such
that c*g(n) ≤ f(n) for all n ≥ n0.

ER-DSP-Analysis of Algorithms Page 3


Examples:
1. 3n+2= Ω(n) as 3n+2>=3n for all n>=1

2. 3n+3= Ω(n) as 3n+3>=3n for all n>=1

3. 100n+6= Ω(n) as 100n+6>=100n for all n>=1

4. 10n2 + 4n+2 = Ω(n2) as 10n2 + 4n+2 >=n2for all n>=1

3.Theta Notation (Θ-Notation):


 It represents the upper and the lower bound of the
running time of an algorithm.
ER-DSP-Analysis of Algorithms Page 4
 It is used for analyzing the average-case complexity
of an algorithm.
Let g and f be the function from the set of natural
numbers to itself. The function f is said to be Θ(g), if
there are constants c1, c2 > 0 and a natural number
n0 such that c1* g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0.

Example:
1. 3n+2= ө(n)as3n+2>=3n for all n>=2 and 3n+2<=4n for all
n>=2

2. 3n+3= ө(n)

ER-DSP-Analysis of Algorithms Page 5


3. 100n+6= ө(n)

4. 10n2 + 4n+2 = ө(n2)

5. 6*2n + n2 = ө(2n)

6. 10*log n+4 = ө(log n )

ER-DSP-Analysis of Algorithms Page 6

You might also like