Scribd Logo
Upload

Welcome to Scribd!

  • 11 views

    Bog o Notation

    Uploaded by

    bigitinfotainment
    bog o notation Analysis of Binary Search Algorithm

    Copyright:

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

    Bog o Notation

    Uploaded by

    bigitinfotainment
    11 views6 pages
    bog o notation Analysis of Binary Search Algorithm

    Original Title

    bog o notation

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    bog o notation Analysis of Binary Search Algorithm

    Copyright:

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

    Bog o Notation

    Uploaded by

    bigitinfotainment
    bog o notation Analysis of Binary Search Algorithm

    Copyright:

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

    Name : M Arslan

    Class : BS-SE-3-A

    Arid No: 23-arid-4348

    Assignment No: 1

    Topic : Time Complexity of Linear & Binary Searches

    Subject : Data Structure


    Binary Search
    Time and Space Complexity Analysis of Binary Search Algorithm

    Time complexity of Binary Search is O(log n), where n is the number of elements in the array. It
    divides the array in half at each step. Space complexity is O(1) as it uses a constant amount of extra
    space.

    Time Complexity of Binary Search Algorithm:


    Best Case
    O(1)
    Average Case
    O(log N)

    Worst Case
    O(log N)
    Auxiliary Space Complexity of Binary Search Algorithm
    The auxiliary space complexity of the Binary Search Algorithm is O(1), which means it requires a
    constant amount of extra space regardless of the size of the input array. This is because Binary Search
    is an iterative algorithm that does not require any additional data structures or recursion that grows
    with the input size. Although, we can also implement Binary Search recursively.
    Linear Search
    Time and Space Complexity Analysis of Linear Search Algorithm
    The time complexity of the Linear Search algorithm is O(n), where n is the number of elements in
    the array. The space complexity is O(1) as it requires a constant amount of extra space regardless of
    the input size.

    Time Complexity of Linear Search Algorithm


    Best Case
    O(1)
    Best case is when the list or array's first element matches the target element. The time complexity
    is O(1) because there is just one comparison made. So the best case complexity is O(1).
    Average Case
    O(n)
    The average case time complexity of the linear search algorithm is O(n), where n is the number of
    elements in the array being searched.

    Worst Case
    O(n)

    The worst-case will be when the target element is absent from the list or array or is located at the
    end of the list. O(n) time complexity results from the necessity to traverse the complete list and
    the n comparisons that are required.

    Auxiliary Space Complexity of Linear Search Algorithm


    The auxiliary space complexity of the linear search algorithm is O(1), which means it uses a
    constant amount of additional space regardless of the size of the input array.

    You might also like