Discussion
Given an integer array of size N, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is
Answer: A
The worst-case time is both \(O(N)\) and \(\Omega(N)\), that is \(\Theta(N)\).
The algorithm makes a single pass, comparing each element with its neighbour, so it does at most N − 1 comparisons, which is O(N). In the worst case, a sorted array (or one whose first violation is at the very end), every adjacent pair must be checked before the algorithm can answer, so it needs N − 1 comparisons, which is \(\Omega(N)\).
Any correct algorithm must look at every element in the worst case, since an unread element could break the order. So the worst-case cost is linear from both sides, and the options denying either bound are wrong.
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