Design and Analysis of Algorithms 2076 (new)

Complexity of an algorithm is a measure of the amount of time and/or space required by an algorithm for an input of a given size (n). The complexity of an algorithm can be divided into two types: The time complexity and the space complexity.

• Time complexity of an algorithm is the measure of total time required to execute the algorithm.
  
• The space complexity is defined as how much space is required to execute an algorithm.

Asymptotic notations are the general representation of time and space complexity of an algorithm. Majorly, we use three types of Asymptotic Notations and those are as follows:

1. Big-Oh notation:

A function f(n) is said to be “big-Oh of  g(n)” and we write, f(n)=O(g(n)) or simply f=O(g), if there are two positive constants c and n₀ such that f(n)<=c*g(n) for all n>=n_0.

E.g. The big oh notation of  f(n)=n+4 is O(n) since n+4<=2n for all n>=4.

The big oh notation of  f(n)=n²+3n+4 is O(n²) since n²+3n+4<=2n²  for all n>=4.

Big O notation specifically describes worst case scenario. It represents the upper bound running time complexity of an algorithm.

2. Big-Omega notation:

A function f(n) is said to be “big-Omega of  g(n)” and we write, f(n)=Ω(g(n)) or simply f=Ω(g), if there are two positive constants c and n₀ such that f(n)>=c*g(n) for all n>=n_0.

E.g. The big omega notation of f(n)=5n+6  is Ω(n) since 5n+6>=5n for all n>=1.

The big omega notation of f(n)=3n²+2n+4   is Ω(n²) since 3n²+2n+4 >=3n² for all n>=1.

Big-Omega notation specifically describes best case scenario. It represents the lower bound running time complexity of an algorithm. 

3. Big Theta notation:

A function f(n) is said to be “big-Theta of g(n)” and we write, f(n)= Θ(g(n)) or simply f= Θ(g), if there exist positive constants c₁, c₂ and n₀ such that c₁*g(n)<=f(n)<= c₂*g(n) for all n>=n₀.

E.g. The big theta notation of  f(n)=5n+2  is Θ(n) since 6n>=5n+2>=5n for all n>=3.

The big theta notation of f(n)=3n²+2n+1 is Θ(n²) since 4n² >=3n²+2n+1>=3n²² for all n>=3. 

This notation describes both upper bound and lower bound of an algorithm so we can say that it defines exact asymptotic behaviour.

In divide and conquer paradigm, a problem is divided into smaller problems, then the smaller problems are solved independently, and finally the solutions of smaller problems are combined into a solution for the large problem.

Generally, divide-and-conquer algorithms have three parts:

• Divide: Divide the given problem into sub-problems using recursion.
• Conquer: Solve the smaller sub-problems recursively. If the subproblem is small enough, then solve it directly.
• Combine: Combine the solutions of the sub-problems that are part of the recursive process to solve the actual problem.

Example: Some problems which are based on the Divide & Conquer approach are:

• Binary Search
• Sorting (merge sort, quick sort)

Quick sort algorithm using randomized approach

RandQuickSort(A, l, r)

{

    if(l<r)

    {

        m = RandPartition(A, l, r);

        RandQuickSort(A, l, m-1);

        RandQuickSort(A, m+1, r);

    }

}

RandPartition(A, l, r)

{

    k = random(l, r);     //generates random number between i and j including both.

    swap(A[l], A[k]);

    return Partition(A, l, r);

}

Partition(A,l,r)

{

    x =l; y =r ; p = A[l];

    while(x<y)

    {

        do {

                    x++;

            }while(A[x] <= p);

        do {

                    y--;

            } while(A[y] >=p);

        if(x<y)

            swap(A[x],A[y]);

    }

    A[l] = A[y];  A[y] = p;

    return y;         //return position of pivot

}

Time Complexity:

•     Worst Case: T(n) = O(n2)
•     Average Case: T(n) = O(nlogn)