Time complexity of finding 3 smallest elements in less than O(n) comparisons

Question

I've 2 problems regarding determination of time complexity of 2 algorithms.

Problem 1

Determining the smallest 3 numbers from a set of n distinct numbers using comparisons.

1. These 3 elements can be determined using O(log²n) comparisons.
2. O(log²n) don't suffice, however they can be determined using n + O(1) comparisons.
3. n + O(1) don't suffice, however they can be determined using n + O(logn) comparisons.
4. n + O(logn) don't suffice, however they can be determined using O(n) comparisons.
5. None of the above.

Here, the way I thought of it is to take 3 variables (e.g: MIN₁, MIN₂ & MIN₃ where MIN₁ being the smallest & MIN₃ being the largest of these 3), initialize them with the 1^st 3 elements of the list and scan the list once. For each number x in the list we have the following 4 cases:

1. if x < Min₁then, Min₃ = Min₂; Min₂ = Min₁; Min₁ = x;
2. else if Min₁ < x < Min₂then, Min₃ = Min₂; Min₂ = x;
3. else if Min₂ < x < Min₃then, Min₃ = x;
4. else if Min₃ < x then, do nothing

So, basically it'll require 3n comparisons in the worst case and 0 comparison in the best case.

Correct me if it can be done in an otherwise easier (less time bound) way. Actually I'm confused with options 3 and 4.

Problem 2

Determining both the smallest and the largest number from a set of n distinct numbers using comparisons.

1. these 2 elements can be determined using O(log¹⁰⁰n) comparisons.
2. O(log¹⁰⁰n) don't suffice, however they can be determined using n + O(logn) comparisons.
3. n + O(logn) don't suffice, however they can be determined using 3.⌈ⁿ⁄₂⌉ comparisons.
4. 3.⌈ⁿ⁄₂⌉ don't suffice, however they can be determined using 2.(n-1) comparisons.
5. None of the above.

Using analogous argument as before I've come up with the answer 2(n-1). Although I'm still confused between options 2 and 4.

Answer 1

Problem 1: You can improve upon your algorithm to 2n comparisons by first comparing to MIN2. This is still O(n). To see that n+O(1) doesn't suffice, note that there are n*(n-1)*(n-2) possibilities, where MIN1, MIN2, and MIN3 are located. Take logarithm to base 2 to get the lower bound on the number of required comparisons.

Problem 2: This can be done in 3*ceil(n/2) by comparing two successive elements, then comparing the smaller to the current min and the greater to the current max.