11 11 votes Let $S$ be a sorted array of $n$ distinct positive integers. Let $T(n)$ denote the time complexity of the most efficient algorithm to determine if there exist three indices $i<j<k$ such that the condition $S[i]+S[j]>S[k]$ is met. Which of the following is true?$T(n)=O\left(n^3\right)$ $T(n)=O\left(n^2\right)$ $T(n)=O(n \log n)$ $T(n)=O(n)$ Algorithms goclasses algorithms goclasses-cs-dpp goclasses-cs-dpp-day-101 goclasses-algorithms-practice-questions + – GO Classes 893 views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
2 2 votes indireclty the question is speakig about the insertion sorting . In insertion sorting if the array is sorted there will be no inversions(swappings) , so here we will have only time for comparisions is O(n). n comparisions+ 0 inversions=O(n) sriharshamarella452 answered Dec 26, 2025 sriharshamarella452 comment Share Follow See 1 comment 1 1 comment reply edge_weight commented Jun 27 reply Follow flag Nice observation @sriharshamarella452 0 0 replyShare Please log in or register to add a comment.
1 1 vote Loop with an index $i$ from 0 to $n-3$. In each step, check if $S[i]+S[i+1]>S[i+2]$. If this condition is ever met, you can immediately stop because you've found the answer. If the loop completes without finding such a triplet, then no such combination exists. This single pass through the array results in a time complexity of $O(n)$. GO Classes answered Oct 6, 2025 GO Classes comment Share Follow See 1 comment 1 1 comment reply 13Dev commented Oct 6, 2025 reply Follow flag Oh yes.!! It was sorted right..!! 0 0 replyShare Please log in or register to add a comment.
