Scribd Logo
Upload

Welcome to Scribd!

  • 95 views

    Recursive Algorithms and Recurrence Equations

    Uploaded by

    Amogh Vaishnav
    This document discusses recurrence relations and their use in analyzing recursive algorithms and sorting algorithms. It provides recurrence relations for various algorithms like factorial, Fibonacci, bubble sort, selection sort, insertion sort, merge sort, and quicksort. Recurrence relations define the running time of an algorithm in terms of smaller inputs and are useful for determining the time complexity of recursive and sorting algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Recursive Algorithms and Recurrence Equations

    Uploaded by

    Amogh Vaishnav
    95 views5 pages
    This document discusses recurrence relations and their use in analyzing recursive algorithms and sorting algorithms. It provides recurrence relations for various algorithms like factorial, Fibonacci, bubble sort, selection sort, insertion sort, merge sort, and quicksort. Recurrence relations define the running time of an algorithm in terms of smaller inputs and are useful for determining the time complexity of recursive and sorting algorithms.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses recurrence relations and their use in analyzing recursive algorithms and sorting algorithms. It provides recurrence relations for various algorithms like factorial, Fibonacci, bubble sort, selection sort, insertion sort, merge sort, and quicksort. Recurrence relations define the running time of an algorithm in terms of smaller inputs and are useful for determining the time complexity of recursive and sorting algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    95 views5 pages

    Recursive Algorithms and Recurrence Equations

    Uploaded by

    Amogh Vaishnav
    This document discusses recurrence relations and their use in analyzing recursive algorithms and sorting algorithms. It provides recurrence relations for various algorithms like factorial, Fibonacci, bubble sort, selection sort, insertion sort, merge sort, and quicksort. Recurrence relations define the running time of an algorithm in terms of smaller inputs and are useful for determining the time complexity of recursive and sorting algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 5

    Recursive Algorithms and Recurrence

    Equations
    ● Performance of recursive algorithms is typically specified with recurrence equations
    ● Recurrence Equations as known as Recurrence and Recurrence Relations
    o Recurrence relations have specifically to do with sequences (eg Fibonacci
    Numbers)
    o A recurrence relation is an equation that defines a sequence based on a rule
    that gives the next term as a function of the previous term(s).
    Analyzing Recursive Routines
    ● Analysis of recursive routines is not as easy: consider factorial
    fac(n) is
    if n = 1 then return 1
    else return fac(n-1) * 1

    ● How many times is fac called for fac(n)?


    ● To find an answer, Use a recurrence
    Recurrences
    ● A recurrence defines T(n) in terms of T for smaller values
    ● Example: T(n) = T(n-1) + 1
    o T(n) is defined in terms of T(n-1)
    ● Recurrences are used in analyzing recursive algorithms
    ● As known as: Recurrence Equation, Recurrence Relation

    Recurrence Relation for Sorting Algorithms

    ● Recurrence Relation for Bubble Sort


    Pseudo Code for Bubble Sort

    for( i=0 ; i<N-1 ; i++ ){


    for( j=0 ; j<N-i-1 ; j++){
    if( array[i] > array[j] )
    swap( array[i] , array[j] );
    }
    }

    For each iteration of the outer loop, we place the largest element at the end of the array. In
    simple words, the ith iteration of the outer loop move the largest element from the first 
    elements to (N-i-1)th position.

    Recurrence Relation

    T(N) = T(N-1) + (N-1)


    T(N) = T(N-1) + N (ignore constant)

    N is the number of steps required to place the largest element at the end of the array
    and T(N-1) signifies that time required to sort the rest of N-1 elements.
    ● Recurrence Relation for Selection Sort
    ● In each iteration of selection sort, we search for the smallest element and place it at the
    beginning of the array. After that, we increment the beginning position of the array and again
    search for the smallest element among the rest of the elements and repeat.
    ● Searching the smallest element in the array takes N-1 comparisons.

    Recurrence Relation

    T(N) = T(N-1) + N-1


    T(N) = T(N-1) + N

    N is the time required to search the smallest element in the array and place it at the beginning
    of the array. T(N-1) is the time required to sort the rest of the  N-1 elements.

    ● Recurrence Relation for Insertion Sort


    Insertion Sort Pseudo Code

    i=0
    while i < N
    temp = array[i];
    j=i
    // inserting array[i] in the sorted sequence
    while j > 0 && array[j-1] > array[j]
    array[j] = array[j-1];
    j = j - 1;
    end while
    array[j] = temp;
    end while

    The ith iteration of the outer loop implies that we have sorted array till i – 1 index. We need
    to insert the ith element in the sorted elements in the range [0, i-1]. Since the size of the
    sorted portion is i, the insertion requires i – 1 comparison.

    Recurrence Relation

    T(N) = T(N-1) + N

    T(N-1) is the time required to sort N-1 elements. N denotes the time required to insert


    the Nth element in the sorted sequence of N-1 elements.

    ● Recurrence Relation for Merge Sort

    Pseudo Code for Merge Sort

    function merge_sort(array, start, end)


    if(start<end)
    mid = (start + end)/2
    merge_sort(array,start,mid-1)
    merge_sort(array,mid+1,start)
    merge(array,start,end)
    end if
    end function

    On each call of merge_sort, we split the array into two equal parts. Then we recursively sort
    the two parts. After sorting the two halves, we merge them such that the array remains sorted.
    Recurrence Relation

    T(N) = 2 * T(N/2) + N

    2* T(N/2) is the time required to sort the two equal parts of the array. N is the time required
    to merge the two sorted parts into a single sorted array.

    ● Recurrence Relation for Quicksort


    Pseudo Code for Quick Sort

    function quick_sort(array, start, end)


    if(start<end)
    pivot = partition(array,start,end)
    quick_sort(array,start,mid-1)
    quick_sort(array,mid+1,start)
    end if
    end function

    Quicksort first chooses a random element X as the pivot and partition the array in 2 parts
    such that the elements smaller than X are on the left side and elements greater than X are on
    the right side. After partition, X is in the correct position. Then we recursively sort the
    elements on the left side X and elements on the right side of X.

    The partition requires  N comparisons.


    Recurrence Relation

    Best Case
    In the best-case scenario, the pivot will split the array into 2 equal parts. Therefore, the
    recurrence relation will be
    T(N) = 2 * T(N/2) + N
    N comparisons to find the pivot position and  2*T(N/2) to sort the two partitions of the array.
    Worst Case
    In the worst case, the pivot will split the array of size N such that one part will contain no
    element, and the other party will contain N-1 elements. This happens if all the elements are
    either smaller or greater than the pivot element.

    T(N) = T(N-1) + N

    ● Recurrence Relation for Factorial


    Pseudo Code for Factorial
    1. func factorial(n)
    2. if (n == 1)
    3. return 1
    4. return n * factorial(n -1)

    This function written as a recurrence relation is:


    T(n)=1 for n=0
    T(n)=T(n-1) + 1 for n>0
    This recurrence running time in Big O notation is: O(n)

    ● Recurrence Relation for Fibonacci

    Pseudo Code for Fibonacci


    1. func fibonacci(n)
    2. if (n<= 1) then
    3. return 1
    4. else
    5. return (fibonacci(n-1) * fibonacci(n -2)

    This function written as a recurrence relation is:


    T(n) = 0 for n=0
    T(n) = 1 for n=1
    T(n) = T(n-1) + T(n-2) + 2 for n>1
    This recurrence running time in Big O notation is: O(2n)

    ● Recurrence Equations:

    ● Best, Average and Worst Case of Sorting Algorithms


    ● Summation Formula and rule used in Efficiency Analysis

    ● Growth of functions

    You might also like