Time Complexity – While Loop with Three Pointers vs Nested For Loops

algorithm-analysisalgorithmsbig oruby

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(n³)?

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

Best Answer

If looks like a O(n³) 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.