1

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
3

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.

0

You are absolutely correct. The function tries out all possible combinations of elements from the array. In this case, it's O(n³) 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.