New Click here to enroll in UIICL SO Finance and Investment Course

    Register

    Question

    Quick sort average time complexity

    A O(log(N)) Correct Answer Incorrect Answer
    B O(N) Correct Answer Incorrect Answer
    C O(Nlog(N)) Correct Answer Incorrect Answer
    D O(Nlog(N*N)) Correct Answer Incorrect Answer
    E None Correct Answer Incorrect Answer

    Solution

    Quick Sort is a divide-and-conquer algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

    • O(N log(N)) : This is the average time complexity of Quick Sort. The reason is that in an average case, the pivot divides the array into two nearly equal parts, and sorting each part takes O(log(N)) divisions, with each division taking O(N) time to partition the array.
    • O(N) : This represents linear time complexity, which is not the case for Quick Sort.
    • O(log(N)) : This represents logarithmic time complexity, which does not apply to sorting an array.
    • O(N log(N*N)) : This is not a standard time complexity notation for sorting algorithms.
    • none : This is incorrect because the average time complexity of Quick Sort is well-known to be O(N log(N)).
    Hence, the correct answer is: Option (1) O(N log(N))

    Practice Next