0 votes 0 votes Given an Unsorted array, Find maximum in less than O(n) time? How can we do this? Algorithms interview array algorithm-design + – Learner_jai asked Nov 27, 2018 • retagged Jun 11, 2022 by Arjun Learner_jai 488 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply goxul commented Nov 27, 2018 reply Follow Share It's not possible - you'll have to look at every element once so the lower bound for this is $\Omega(n)$. 1 votes 1 votes Swapnil Naik commented Nov 27, 2018 reply Follow Share @goxul it should take $\Theta (n)$ and not $\Omega (n)$ to find maximum and minimum as we always have to search through all numbers. 0 votes 0 votes goxul commented Nov 27, 2018 reply Follow Share $\Theta(n)$ also implies that $\Omega(n)$ holds, @Swapnil Naik 0 votes 0 votes Swapnil Naik commented Nov 27, 2018 reply Follow Share Yes, but Θ(n) would be more appropriate for a given condition. 0 votes 0 votes logan1x commented Jul 11, 2019 reply Follow Share Bubble Sort won't be right because it will take at least O(n) time right? Am I doing anything wrong here? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes I think a simple looping through the array once is enough FindMax( A[] ): max=A[0] for i in A: if(i>max): max=i return max Gatecel answered Jul 11, 2019 Gatecel comment Share Follow See all 0 reply Please log in or register to add a comment.