Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 3 views

    F (N Best Case ( ) Average Case ( ) Worst Case (O)

    Uploaded by

    raspberry R
    This document analyzes the best, average, and worst case time complexities of various functions. It provides the upper and lower bounds for each function in each case and determines the overall worst case time complexity as O(n), O(n^2), or O(n^3) based on the largest term.

    Copyright:

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

    F (N Best Case ( ) Average Case ( ) Worst Case (O)

    Uploaded by

    raspberry R
    3 views3 pages
    This document analyzes the best, average, and worst case time complexities of various functions. It provides the upper and lower bounds for each function in each case and determines the overall worst case time complexity as O(n), O(n^2), or O(n^3) based on the largest term.

    Original Description:

    Original Title

    DAA.docx

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document analyzes the best, average, and worst case time complexities of various functions. It provides the upper and lower bounds for each function in each case and determines the overall worst case time complexity as O(n), O(n^2), or O(n^3) based on the largest term.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    3 views3 pages

    F (N Best Case ( ) Average Case ( ) Worst Case (O)

    Uploaded by

    raspberry R
    This document analyzes the best, average, and worst case time complexities of various functions. It provides the upper and lower bounds for each function in each case and determines the overall worst case time complexity as O(n), O(n^2), or O(n^3) based on the largest term.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 3

    F(n)

    Best case()

    Average case
    ()

    2n + 3

    2n <= f(n)
    T(n) = (n)
    n=1

    2n <= f(n) <=


    3n
    T(n) = (n)

    10 n2 + 7

    10 n2 <= f(n)
    T(n) = (n2 )
    n=1

    7n + 5

    7n <= f(n)
    T(n) = (n)
    n=1

    27n 2+ 16

    27n2 <= f(n)


    T(n) = (n2 )
    n=1

    27n2 + 16n + 25

    27n2 <= f(n)


    T(n) = (n2 )
    n=1

    Worst case(O)

    F(n) <= 2n + 3
    <= 2n + n
    <= 3n
    (3 <= n)
    T(n) = O(n) , n =
    3
    2
    10n <= f(n) <=
    F(n) <= 10n2 + 7
    11n2
    <= 10n2 + n
    T(n) = (n2 )
    <= 11n2
    ( n <= n2 )
    T(n) = O(n2 ) , n
    =3
    7n <= f(n) <= 8n F(n) <= 7n + 5
    T(n) = (n)
    <= 8n
    (5 <= n)
    T(n) = O(n), n =
    5
    2
    27n <= f(n) <= F(n) <= 27n2 +
    28n2
    16
    2
    T(n) = (n )
    <= 27n2 +
    n2
    (n <= n2)
    <= 28n2
    T(n) = O(n2 ), n =
    4
    27n2 <= f(n) <=
    F(n) <= f(n)
    2
    28n
    <= 27n2 +
    T(n) = (n2 )
    17n
    (15 <= n)
    <= 28n2
    T(n) = O(n2 ), n =
    18

    4n3 + 2n + 3

    4n3 <= f(n)


    T(n) = (n3 )
    n=1

    4n3 <= f(n) <=


    5n3
    T(n) = ( n3 )

    F(n) <= f(n)


    <= 4n3 + 3n
    (3 <= n)
    <= 4n + n
    ( n <= n2)
    <= 5n3
    ( n2 <= n3)
    T(n) = O(n3 ), n =
    2

    3n + 4n

    3n <= f(n)
    T(n) = (n3 )
    n=1

    3n <= f(n) <=


    4n3
    T(n) = (n3 )

    5n3 + n2 + 3n + 2 5n3 <= f(n)


    T(n) = (n3 )
    n=1

    5n3 <= f(n) <=


    6n3
    T(n) = (n3)

    2n + 6n2 + 3n

    2n <= f(n)
    T(n) = (2n)
    n=1

    2n <= f(n) <=


    2*2n
    T(n) = (2n)

    F(n) <= f(n)


    <= 3n3 + 4n
    <= 3n3 + n3
    (n2 <= n3)
    <= 4n3
    T(n) = O(n3 ), n =
    2
    F(n) <= f(n)
    <= 5n3 + n2
    + 4n
    (2 <= n)
    <= 5n3 +
    2n2
    <= 6n3
    ( n2 <= n3)
    T(n) = O(n) ,n =
    3
    F(n) <= f(n)
    <= 2n + 6n2
    + n2
    (n <= n2)
    <= 2n + 7n2
    <= 2*2n
    T(n) = O(2n), n =
    10

    4*2

    + 3n

    4*2 <= f(n)


    T(n) = (2n)
    n=1

    4*2 <= f(n) <=


    5*2n
    T(n) = (2n)

    F(n) <= f(n)


    <= 4*2n +
    3n
    <=4* 2n +
    2n

    3*2n + 4n2 + 5n
    +3

    3*2n <= f(n)


    T(n) = (2n)
    n=1

    3*2n <= f(n) <=


    4*2n
    T(n) = (2n)

    6*2n + 6

    6*2n <= f(n)


    T(n) = (2n)
    n=1

    6*2n <= f(n) <=


    7*2n
    T(n) = (2n)

    <= 5*2n
    T(n) = O(2n), n =
    4
    F(n) <= f(n)
    <= 3*2n +
    4n2 +6n
    <=3* 2n +
    5n2
    <= 4*2n
    T(n) = O(2n), n =
    9
    F(n) <= f(n)
    <= 6*2n + n
    <=6* 2n +
    2n
    <= 7*2n
    T(n) = O(2n), n
    =3

    You might also like