Scribd Logo
Upload

Welcome to Scribd!

  • 6 views

    4 - Complexity Analysis

    Uploaded by

    ahsanmusiclover
    Complexity analysis

    Copyright:

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

    4 - Complexity Analysis

    Uploaded by

    ahsanmusiclover
    6 views4 pages
    Complexity analysis

    Original Title

    4- Complexity Analysis

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Complexity analysis

    Copyright:

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

    4 - Complexity Analysis

    Uploaded by

    ahsanmusiclover
    Complexity analysis

    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 4

    Time and Space Complexity of Sequential/Linear Search Algorithm:

    Time Complexity:

     Best Case: In the best case, the key might be present at the first index. So the best case complexity is O(1)

     Worst Case: In the worst case, the key might be present at the last index i.e., opposite to the end from which the
    search has started in the list. So the worst-case complexity is O(N) where N is the size of the list.

     Average Case: O(N)

    Auxiliary Space: O(1) as except for the variable to iterate through the list, no other variable is used.

    Applications of Sequential/Linear Search Algorithm:

     Unsorted Lists: When we have an unsorted array or list, Sequential/Linear search is most commonly used to find any
    element in the collection.

     Small Data Sets: Sequential/Linear Search is preferred over binary search when we have small data sets with

     Simple Implementation: Sequential/Linear Search is much easier to understand and implement as compared to
    Binary Search or Ternary Search.

    Advantages of Sequential/Linear Search Algorithm:

     Sequential/Linear search can be used irrespective of whether the array is sorted or not. It can be used on arrays of
    any data type.

     Does not require any additional memory.

     It is a well-suited algorithm for small datasets.

    Disadvantages of Sequential/Linear Search Algorithm:

     Sequential/Linear search has a time complexity of O(N), which in turn makes it slow for large datasets.

     Not suitable for large arrays.

    When to use Sequential/Linear Search Algorithm?

     When we are dealing with a small dataset.


     When you are searching for a dataset stored in contiguous memory.

    Complexity Analysis of Binary Search Algorithm:

     Time Complexity:

     Best Case: O(1)

     Average Case: O(log N)

     Worst Case: O(log N)

     Auxiliary Space: O(1), If the recursive call stack is considered then the auxiliary space will be O(logN).

    Applications of Binary Search Algorithm:

     Binary search can be used as a building block for more complex algorithms used in machine learning, such as
    algorithms for training neural networks or finding the optimal hyperparameters for a model.

     It can be used for searching in computer graphics such as algorithms for ray tracing or texture mapping.

     It can be used for searching a database.

    Advantages of Binary Search:

     Binary search is faster than Sequential/Linear search, especially for large arrays.

     More efficient than other searching algorithms with a similar time complexity, such as interpolation search or
    exponential search.

     Binary search is well-suited for searching large datasets that are stored in external memory, such as on a hard drive
    or in the cloud.

    Disadvantages of Binary Search:

     The array should be sorted.

     Binary search requires that the data structure being searched be stored in contiguous memory locations.

     Binary search requires that the elements of the array be comparable, meaning that they must be able to be ordered.
    Complexity Analysis of Selection Sort

    2
    Time Complexity: The time complexity of Selection Sort is O(N ) as there are two nested loops:

     One loop to select an element of Array one by one = O(N)

     Another loop to compare that element with every other Array element = O(N)

    2
     Therefore overall complexity = O(N) * O(N) = O(N*N) = O(N )

    Auxiliary Space: O(1) as the only extra memory used is for temporary variables while swapping two values in Array. The
    selection sort never makes more than O(N) swaps and can be useful when memory writing is costly.

    Advantages of Selection Sort Algorithm

     Simple and easy to understand.

     Works well with small datasets.

    Disadvantages of the Selection Sort Algorithm

    2
     Selection sort has a time complexity of O(N ) in the worst and average case.

     Does not work well on large datasets.

     Does not preserve the relative order of items with equal keys which mean it is not stable.
    Complexity Analysis of Bubble Sort :

    2
    Time Complexity: O(N )
    Auxiliary Space: O(1)

    Advantages of Bubble Sort :

     Bubble sort is easy to understand and implement.

     It does not require any additional memory space.

     It is a stable sorting algorithm, meaning that elements with the same key value maintain their relative order in the
    sorted output.

    Disadvantages of Bubble Sort :

     Bubble sort has a time complexity of O(N2) which makes it very slow for large data sets.

     Bubble sort is a comparison-based sorting algorithm, which means that it requires a comparison operator to determine
    the relative order of elements in the input data set. It can limit the efficiency of the algorithm in certain cases.

    You might also like