This page looks best with JavaScript enabled

## Introduction to Algorithms(Asymptotic Analysis)-Part 1

·  ☕ 3 min read  ·  🤖 Arjit Sharma

## Inroduction to Data Structures -

A programming language has data types → int,float,double etc which reduces the coding effort
Data Types are of 2 types :

• Primitive Datatypes → System defined types ex- int,float,array etc
• User Defined Datatypes → User defined types. ex - structures in C,classes in java

### What are Data Structures ?

A way of sorting and organizing data in computer so that it can be used efficiently in order to solve certain problems.

### Abstract Data Types(ADT):

To simplify problem solving, data structures are usually combined with the operations that can be performed on them. This is called ADT.
Ex - Stack data structure with operations like push() and pop()

Just like how primitive type int and operations on this type like addition(+),subtraction(-) etc can be done, ADTs are the same thing just user defined.

## What are Algorithms ?

Step by step unambiguous instructions to solve a given problem.

An algorithm can be judged on:

• Correctness - Gives correct result in finite number of steps
• Efficiency - Time and Space efficient algorithms.

### What is Rate of Growth ?

Rate at which running time increases as function of input(as input increases, time to execute increases) is called rate of growth.

## Why to analyze Algorithms ?

Main Goal - “To compare algorithms in terms of running time and memory”
If we dont analyze algorithms, how will we know which among 2 algo is better for the problem at hand.

Note - Dont run after less time complexity, look for problem statment and requirement

## How to compare algorithms -

In order to compare 2 algorithms ideally such that it is independent of machine and programming style -
We can express running time of given algorithm as a function of input size n and compare different functions corresponding to running time.
"Expressing algorithm in form of expression"

Problem is same algorithm can be expressed using multiple expression.
Example - This is a search algorithm

 1 2 3 4 5 6 7 8  int search(int arr[], int n, int x) { int i; for (i = 0; i < n; i++) if (arr[i] == x) return i; return -1; } 

The above algorithm can be expressed as

• f(n)=n in case of worst case(element found at last)
• f(n)=1 in case of best case(element found first)

To solve this problem and analyze algorithms in a more standard way we need some sort of Syntax and here comes into play "Asymptotic Analysis"

## Asymptotic Notations

Simplifying analyis of runtime by getting rid of details, which may be affected by certain implementation details

If f(n) if expression of algorithm where n is input size, asymptotic analysis means approximating f(n) at higher value of n.

### Big-O Notation : Worst case time complexity

"We are trying to find another function g(n) which approximates f(n) at higher value of n(Input size)"

$f(n)=Ω(g(n))$ if there exists positive constant c & n0 such that c g(n) ≤ f(n) for n≥n0

After certain input size n0, g(n) becomes upper bound of f(n)

### Omega-Ω Notation : Best case time complexity

$f(n)=Ω(g(n))$ if there exists positive constant c & n0 such that c g(n) ≤ f(n) for n≥n0

### Theta-θ Notation : Average case time complexity

$f(n)=Ω(g(n))$ if there exists positive constant c & n0 such that c g(n) ≤ f(n) for n≥n0

Reached end? Why not read Part 2

Referrences

Share on

WRITTEN BY
Arjit Sharma
Yo, I am a CS enthusiast or am I ? Just kidding.