Question 13 Which of the below given statement(s) is/are true?
Micron technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Which of the below given statement(s) is/are true?
I) In bubble sort some data has to be kept in auxiliary memory such as hard disk.
II) Bubble sort can be implemented to get O(n) as best case time complexity.
Show answer & explanation
Statement I is false: Bubble sort is an in-place sorting algorithm that only requires O(1) auxiliary space; no hard disk or external memory is needed. Statement II is true: When the input array is already sorted, an optimized bubble sort with a swap flag can detect this and terminate in O(n) time on the first pass. Therefore, only statement (II) is true.
Step-by-step Derivation:
Analysis of each statement:
Statement I: Bubble sort space complexity
- Bubble sort is an in-place sorting algorithm
- It only needs a constant amount of extra memory for loop counters and temporary swap variables
- Space complexity: O(1) auxiliary space
- No hard disk or external memory is required
- Conclusion: Statement I is FALSE
Statement II: Bubble sort best-case time complexity
- Standard bubble sort: O(n²) in all cases
- Optimized bubble sort with early termination flag:
- Add a boolean flag to detect if a swap occurred in a pass
- If no swap occurs in a pass, the array is sorted
- For an already sorted array, only 1 pass is needed
- Best case: O(n) when array is already sorted
- Conclusion: Statement II is TRUE
Final answer: Only (II) is true → Option A