## Overview

- Basics of function
- Measuring Algorithm Performance
- Why analysis is required
- Types of algorithm analysis
- Time complexity
- Asymptotic Analysis
- Asymptotic Notations
- Calculation Big 0 notation

## Basic Of Functions

T = f(n) [ y = f(x) ]

## Measuring Performance Of Algorithms

Algorithm analysis is an important part of computational complexity theory, which provides theoretical estimate’mfor the required resources of an algorithm to solve a specific computational problem

It is the determination of the amount of time and space resources required to execute it .

It is the determination of the amount of time and space resources required to execute it .

## Why Analysis Is Required?

## Types of Algorithm Analysis

1) Best case

2) Worst case

3) Average case
Certain input takes less time for an algorithm to accomplish its task .This is best case
Certain input takes Max time for an algorithm to accomplish its task .This is worst case
All other cases /total no.of cases = Average case

2) Worst case

3) Average case

## Time Complexity

It is a measure of rate of change in time with respect to change in input size

Various asymptotic notations are there to represent time complexity of an algorithm.

## Asymptotic Analysis

we donot calculate the actual time taken by the algorithm to solve the problem, rather we are interested in how the time taken by an algorithm increases with the input size

## Asymptotic Notation

**1) Big O Notation**

provides an upper bound on the growth rate of time . It represent the worst case scenario

**2) Omega Notation**

provides a lower bound on the growth rate of time. It represents the best case scenario

**3) Theta Notation**

provides both an upperbound and lowerbound on the growth rate of time. It represents the average case scenario .

c1 * g(n) <= f(n) <= c2 * g(n)
here, c1 and c2 are positive constant
for all n >= n0

if g(n) = 3n

then

g(n) = n

if g(n) = 3n

^{3}+ 5n^{2}+ 4then

g(n) = n

^{3}^{for some no such that n>=n0}## Big O Notation

O <= f(n) <= g(n)

for all n >= n0

## Omega Notation

c * g(n) <= f(n)

for all n >= n0

## Calculate O(n)

1) Factorial

2) Insertion Sort

` ````
```f=1
for i=1 to n
f=f*i;
for(i=1 to n)
temp=A[i]
for(j=i-1 to 0)
if(A[j]>temp)
A[j+1]=A[j];
else
break;
A[j+1]=temp;
o(1) o(log n) o(n) o(n logn)
o(n2) o(n2log n) o(n3)
o(a4)