The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
76 views
Given an Unsorted array, Find maximum in less than O(n) time?

How can we do this?
in Algorithms by Active (2.6k points) | 76 views
+1
It's not possible - you'll have to look at every element once so the lower bound for this is $\Omega(n)$.
0
@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

$\Theta(n)$ also implies that $\Omega(n)$ holds, @Swapnil Naik

0

Yes, but Θ(n) would be more appropriate for a given condition.

0
Bubble Sort won't be right because it will take at least O(n) time right? Am I doing anything wrong here?

1 Answer

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

 

by (11 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,092 questions
55,292 answers
190,811 comments
86,118 users