Is the time complexity of a while loop with three pointers different than 3 nested for loops?

Question

This program (written in ruby) finds the largest 3 numbers in an array (without sorting the array). It has a while loop with three pointers. My fist instinct, since there is only one loop is to say this solution is O(n). But, the pointer's j and k get reset when they reach n which seems the same as using 3 for loops, so then is it O(n3)?

def greatest_of_3_with_ptrs(a)
 greatest = 0
 greatest_tuple = nil
 i,j,k=0,1,2
 n = a.length-1
 while( true) do
 sum = a[i]+a[j]+a[k]
 if sum > greatest then
 greatest = sum 
 greatest_tuple =[a[i],a[j],a[k]]
 end 
 sum = 0
 if k == n then
 j=j+1
 k=j+1
 else
 k+=1 
 end
 if j == n then
 i=i+1
 j=i+1
 k=j+1
 end
 break if k > n || j > n || i==n
 end
 { greatest_tuple: greatest_tuple, greatest: greatest }
end
a =[10,-1,4,2,5,3,0]
expected = 19
print greatest_of_3_ptrs(a)[:greatest] #> 19
print greatest_of_3_ptrs(a)[:greatest_tuple] #> [10,4,5]

Please Note: I am aware of the O(n) solution, that is not my question

def greatest(a)
 max_1,max_2,max_3 = a[0],a[1],a[2] 
 for i in 3..a.length-1
 if a[i] > max_1 then
 max_1 = a[i]
 elsif a[i] > max_2 then
 max_2 = a[i]
 elsif a[i] > max_3 then
 max_3 = a[i]
 end 
 end
 [max_1,max_2,max_3]
end

Answer 1

If looks like a O(n3) solution. Your instinct is correct: by resetting variables you are looping. Note: if we only consider the loop instruction we would, mistakenly, think it was O(∞).

However the problem is O(n). Therefore you can do better.

Answer 2

You are absolutely correct. The function tries out all possible combinations of elements from the array. In this case, it's O(n3) and would be of an even higher power, if you wrote a similiar function for the greatest 4, 5, .. elements. The best solution for any of these problems should be of the order O(n).

I just want to mention that in your example for an O(n) solution you omitted the "down-shift" when replacing a value:

def greatest(a)
 max_1,max_2,max_3 = a[0..2].sort.reverse #changed
 for i in 3..a.length-1
 if a[i] > max_1 then
 max_3 = max_2 #new
 max_2 = max_1 #new
 max_1 = a[i]
 elsif a[i] > max_2 then
 max_3 = max_2 #new
 max_2 = a[i]
 elsif a[i] > max_3 then
 max_3 = a[i]
 end 
 end
 [max_1,max_2,max_3]
end