Scribd Logo
Upload

Welcome to Scribd!

  • 5 views

    Lec 1

    Uploaded by

    lorene7910

    Copyright:

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

    Lec 1

    Uploaded by

    lorene7910
    5 views20 pages

    Original Title

    lec 1

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    5 views20 pages

    Lec 1

    Uploaded by

    lorene7910

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 20

    Data Structures

    Lecture: Asymptotic Notations & Complexity Analysis

    By
    Arvind Kumar
    Asst. Professor,
    Lovely Professional University, Punjab
    Contents
    • Basic Terminology
    • Complexity of Algorithm
    • Asymptotic Notations
    • Review Questions
    Basic Terminology
    • Algorithm: is a finite step by step list of well-defined
    instructions for solving a particular problem.

    • Complexity of Algorithm: is a function which gives running


    time and/or space requirement in terms of the input size.

    • Time and Space are two major measures of efficiency of an


    algorithm.
    Algorithm

    Specification of Output
    Specification of Input
    (e.g. any sequence of natural Algorithm as a function of Input
    numbers) (e.g. sequence of sorted
    natural numbers)
    Characteristics of Good Algorithm
    • Efficient
    • Running Time
    • Space used

    • Efficiency as a function of input size


    • Size of Input
    • Number of Data elements
    Time-Space Tradeoff
    • By increasing the amount of space for storing the
    data, one may be able to reduce the time needed for
    processing the data, or vice versa.
    Complexity of Algorithm
    • Time and Space used by the algorithm are two main
    measures for efficiency of any algorithm M.

    • Time is measured by counting the number of key


    operations.

    • Space is measured by counting the maximum of


    memory needed by the algorithm.
    • Complexity of Algorithm is a function f(n) which gives
    running time and/or space requirement of algorithm M in terms
    of the size n of the input data.

    • Worst Case: The maximum value of f(n) for any possible input.

    • Average Case: The expected or average value of f(n).

    • Best Case: Minimum possible value of f(n).


    Analysis of Insertion Sort Algorithm
    cost times
    for j←2 to n do c1 n
    key ←A[j] c2 n-1
    i ←j-1 c3 n-1
    while i>0 and A[i] > key c4
    do A[i+1] ←A[i] c5
    i-- c6
    A[i+1] ← key c7 n-1
    Total Time = n(c1 + c2 + c3 + c7) +
    - (c2 + c3 + c5 + c6 + c7)
    Analysis of Insertion Sort
    Total Time = n(c1 + c2 + c3 + c7) +
    - (c2 + c3 + c5 + c6 + c7)
    • Best Case: Elements are already sorted, tj=1
    running time = f(n)
    • Worst Case: Elements are sorted in reverse order,
    tj=j
    running time = f(n2)
    • Average Case: tj= j/2
    running time = f(n2)
    Rate of Growth
    • The rate of growth of some standard functions
    g(n) is:

    log2n < n < nlog2n < n2 < n3 < 2n


    Analysis of Algorithms
    • // Here c is a constant
    for (int i = 1; i <= c; i++)
    {
    // some O(1) expressions
    }

    • O(1): Time complexity of a function (or set of


    statements) is considered as O(1) if it doesn’t
    contain loop, recursion and call to any other
    function.
    Analysis of Algorithms
    • for (int i = 1; i <= n; i += c)
    { // some O(1) expressions }

    • for (int i = n; i > 0; i -= c)


    { // some O(1) expressions }

    • O(n): Time Complexity of a loop is considered as


    O(n) if the loop variables is incremented /
    decremented by a constant amount.
    Analysis of Algorithms
    • for (int i = 1; i <=n; i += c)
    {
    for (int j = 1; j <=n; j += c)
    { // some O(1) expressions
    }
    }
    • for (int i = n; i > 0; i -= c)
    {
    for (int j = i+1; j <=n; j += c)
    { // some O(1) expressions
    } }
    • O(n2): Time complexity of nested loops is equal to the
    number of times the innermost statement is executed.
    Analysis of Algorithms
    • for (int i = 1; i <=n; i *= c)
    { // some O(1) expressions }

    • for (int i = n; i > 0; i /= c)


    { // some O(1) expressions }

    • O(Logn) Time Complexity of a loop is


    considered as O(Logn) if the loop variables is
    divided / multiplied by a constant amount.
    Analysis of Algorithms
    • for (int i = 2; i <=n; i = pow(i, c))
    { // some O(1) expressions }

    • //Here fun is sqrt or cuberoot or any other


    constant root
    for (int i = n; i > 0; i = fun(i))
    { // some O(1) expressions }
    • O(LogLogn) Time Complexity of a loop is
    considered as O(LogLogn) if the loop variables is
    reduced / increased exponentially by a constant
    amount.
    Analysis of Algorithms
    • for (int i = 2; i*i <=n; i++))
    { // some O(1) expressions }

    • O(√n) Time Complexity.


    Questions
    Review Questions
    • When an algorithm is said to be better than the
    other?

    • Can an algorithm have different running times on


    different machines?

    • How the algorithm’ running time is dependent on


    machines on which it is executed?
    Review Questions
    Find out the complexity:
    function ()
    {
    if (condition)
    {
    for (i=0; i<n; i++) { // simple statements}
    }
    else
    {
    for (j=1; j<n; j++)
    for (k=n; k>0; k--) {// simple statement}
    }
    }

    You might also like