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

Big-O Notation
Big-O-Notation: Big-O Notation

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

Big-Omega Notation
Big-Omega-Notation: Big-Omega Notation

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

Big-Theta Notation
Big-Theta-Notation: Big-Theta Notation

Reached end? Why not read Part 2


Referrences

  1. Cornell article

  2. IIT notes .

  3. Narsimha Karumanchi book


Share on

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


What's on this Page