Discussion
Consider an array \(A\) of integers of size \(n\). The indices of \(A\) run from 1 to \(n\). An algorithm is to be designed to check whether \(A\) satisfies the condition given below.
\(\forall i,j \in \{1,\ldots,n-1\}\) such that \(i \gt j\), \((A[i+1] - A[i]) \gt (A[j+1] - A[j])\)
Which one of the following gives the worst case time complexity of the fastest algorithm that can be designed for the problem?
Answer: A
The fastest algorithm takes Θ(n) in the worst case.
Write di = A[i+1] - A[i] for i = 1, ..., n - 1. The condition says di > dj whenever i > j: the sequence of differences is strictly increasing. Strict increase of a whole sequence is equivalent to strict increase between each pair of neighbours, di+1 > di, because the relation > is transitive. So one pass computing the n - 1 differences and comparing neighbours suffices: O(n).
No algorithm can do better, since changing any single element of A can break the condition, so every element must be read: Ω(n). Checking all pairs (i, j) would take Θ(n2), and Θ(log n) is impossible for the same reason.
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