How can I write an O(1) algorithm to return an element NOT smallest in array?

Question

Given an array of unique elements = [ 2, 6, 11, 21, 5 ]. How can I write an O(1) algorithm that returns an element that is not the smallest in the array?

//  I tried... but not sure if this is O(1)   -  runtime

$arr = [2, 6, 11, 21, 5];
$smallest = $arr[0];

function returnSmallest() {

   for( i = 1; i < $arr.length; i++ )  
   {
      if($arr[i] < $smallest)
   {
     $smallest = $arr[i];
   }
}  return $smallest;

}();

print($smallest);

If you want an element which is not the smallest, just compare the two first elements. O(1) ! — Damien
– Damien, Commented Nov 20, 2019 at 16:42
Yes, should return an element that is NOT smallest in the array (correction to the title). I am not sure if my attempt at writing the code /algorithm is correct and represents a runtime of O(1) — Mr CEO
– Mr CEO, Commented Nov 20, 2019 at 16:49
@MrCEO, your code is O(n) since you are looping over the entire array, Damien's answer is correct you can just compare first 2 items in array and return the largest ( which btw is O(1) ) — Pavan Skipo
– Pavan Skipo, Commented Nov 20, 2019 at 16:52
Your code returns the smallest element. It is O(n) as it examines the n elements. Impossible to do better if you want the smallest, as you need to examine all elements in this case. You don't need to examine all elements if you simply want an element which is not the smallest — Damien
– Damien, Commented Nov 20, 2019 at 16:52
@MrCEO It's simple when u compare 2 elements and you return the largest, then obviously other element is smaller right? which satisfies your condition "return NOT smallest item in array". let me give as example [10, 4, 3, 11] --> (10 > 4) ---> return(10) which is not the smallest in array. — Pavan Skipo
– Pavan Skipo, Commented Nov 20, 2019 at 17:03

user3314148 · Accepted Answer · 2019-11-20 16:54:28Z

3

Your question is vague. If you want to return the smallest element, there is no O(1) algorithm to do that if you are not storing the elements in a sorted array.

If you want to return an element that is not smallest, your code is wrong, since it is returning the smallest element. You can just return the largest between the first two elements and that is O(1).

answered Nov 20, 2019 at 16:54

user3314148

1076 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How can I write an O(1) algorithm to return an element NOT smallest in array?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related