Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

TECHNICAL REPORT WRITING OF
IMPACT OF ASYMPTOTIC NOTATION
IN THE FIELD OF TIME
COMPLEXITY ANALYSIS OF ALGORITHM

SUBMITTED BY
NAME:- AYUSH GAURAV
DEPARTMENT:- ECE
SEMESTER:- 4th
UNIVERSITY ROLL NO:- 16900321137

Department of ECE
Academy of Technology
Aedconagar, Hooghly-712121
West Bengal, India

❑ ABSTRACT
❖ In this presentation , we will discuss what asymptotic notations are
...

❖ The efficiency of an algorithm depends on the amount of time, storage
and other resources required to execute the algorithm
...

❖ An algorithm may not have the same performance for different types of
inputs
...

❖ The study of change in performance of the algorithm with the change in
the order of the input size is defined as asymptotic analysis
...
We should not calculate the exact running
time, but we should find the relation between the running time and the input
size
...
For
the space complexity, our goal is to get the relation or function that how much
space in the main memory is occupied to complete the algorithm
...
To perform better, you need to write algorithms that are time efficient
and use less memory
...
Domain and range of this
function are generally expressed in natural units
...
The time complexity of an algorithm is the
amount of time it takes for each statement to complete
...
It also aids in defining an
algorithm's effectiveness and evaluating its performance
...
The amount of memory used by a program to execute it is
represented by its space complexity
...

For example: In bubble sort, when the input array is already sorted, the
time taken by the algorithm is linear i
...
the best case
...
e
...

When the input array is neither sorted nor in reverse order, then it takes
average time
...

There are mainly three asymptotic notations:
•

Big-O notation

•

Omega notation

•

Theta notation

➢ Big-O Notation (O-notation)
Big-O notation represents the upper bound of the running time
of an algorithm
...


O(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }

The above expression can be described as a function f(n) belongs to the
set

O(g(n))

between

0

if there exists a positive constant
and

cg(n) ,

C

such that it lies

for sufficiently large n
...


Since it gives the worst-case running time of an algorithm, it is widely used
to analyze an algorithm as we are always interested in the worst-case
scenario
...

The best case time complexity of Insertion Sort is Θ(n)
...
Many times we easily find an upper bound by simply
looking at the algorithm
...


➢ Omega Notation (Ω-notation)
Omega notation represents the lower bound of the running time
of an algorithm
...


Ω(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

The above expression can be described as a function
set

Ω(g(n))

if there exists a positive constant

c

f(n)

belongs to the

such that it lies above

cg(n) ,

for sufficiently large n
...

Let us consider the same Insertion sort example here
...

Examples :
{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Ω( n^2)
U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Ω(n)
U { 100 , log (2000) , 10^4 } belongs to Ω(1)
Note: Here, U represents union, we can write it in these manner because Ω
provides exact or lower bounds
...
Since it
represents the upper and the lower bound of the running time of an
algorithm, it is used for analyzing the average-case complexity of an
algorithm
...


lies anywhere in between

c1g(n)

and

c2g(n)

for all

n ≥ n0 ,

is said to be asymptotically tight bound
...

It exist as both, most, and least boundaries for a given input value
...
For example, Consider the expression 3n3 + 6n2 +
6000 = Θ(n3), the dropping lower order terms is always fine because there will
always be a number(n) after which Θ(n3) has higher values than Θ(n2) irrespective
of the constants involved
...
Examples :
{ 100 , log (2000) , 10^4 } belongs to Θ(1)
{ (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Θ(n)
{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Θ( n2)
Note: Θ provides exact bounds
...
General Properties:
If f(n) is O(g(n)) then a*f(n) is also O(g(n)), where a is a constant
...

Similarly, this property satisfies both Θ and Ω notation
...

If f(n) is Ω (g(n)) then a*f(n) is also Ω (g(n)), where a is a constant
...
Transitive Properties:
If f(n) is O(g(n)) and g(n) is O(h(n)) then f(n) = O(h(n))
...

We can say,
If f(n) is Θ(g(n)) and g(n) is Θ(h(n)) then f(n) = Θ(h(n))
...
Reflexive Properties:
Reflexive properties are always easy to understand after transitive
...
Since MAXIMUM VALUE OF f(n) will be f(n)
ITSELF!
Hence x = f(n) and y = O(f(n) tie themselves in reflexive relation always
...
e O(f(n))
Similarly, this property satisfies both Θ and Ω notation
...

If f(n) is given then f(n) is Ω (f(n))
...
Symmetric Properties:
If f(n) is Θ(g(n)) then g(n) is Θ(f(n))
...

5
...

Example:
If(n) = n , g(n) = n²
then n is O(n²) and n² is Ω (n)
This property only satisfies O and Ω notations
...
Some More Properties:
1
...
If f(n) = O(g(n)) and d(n)=O(e(n)) then f(n) + d(n) = O( max( g(n), e(n) ))
Example:
f(n) = n i
...
e O(n²)
then f(n) + d(n) = n + n² i
...
If f(n)=O(g(n)) and d(n)=O(e(n)) then f(n) * d(n) = O( g(n) * e(n))
Example:
f(n) = n i
...
e O(n²)
then f(n) * d(n) = n * n² = n³ i
...
As we build more complicated programs the
performance requirements change and become more
complicated and asymptotic analysis may not be as useful
...
Using these, we
represent the upper bound or lower bound of run-time in
mathematical equations and thus help us perform our
task with the best efficiency and fewer efforts
...
Design and analysis of algorithms-Gajendra Sharma,Khanna
Publishing house
...
algorithm design:foundations,analysis,and internet examples
Second edition,Michael T Goodrich and Roberto tamassia,wiley
...
wikipedia
4
...
study material



---