Discussion
Consider an array consisting of -ve and +ve numbers. What would be the worst case time complexity of an algorithm to segregate the numbers having same sign altogether i.e all +ve on one side and then all -ve on the other ?
Answer: A
Correct answer: O(N)
Segregating the numbers needs only a single partition pass: keep one index scanning forward and one backward, and swap whenever a positive on the left meets a negative on the right. Each element is examined once, so the worst case is \(O(N)\). Sorting would also separate them, but at \(O(N \log N)\) it does more work than the question requires.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development