Advertisement
Guest User

learning big o notation

a guest
Sep 3rd, 2014
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Ruby 0.53 KB | None | 0 0
  1. def count_ones(a_list)
  2.   total = 0  # O(1) + O(1)  -- constant store + constant fetch for object '0'
  3.   a_list.each do |e| # O(n) -- because it increases linearly with input
  4.     if e == 1        # O(1) -- because binary operations are constants
  5.       total += 1     # O(1) + O(1) + O(1) + O(1) -- constant fetch, constant fetch, binary operation (+), constant store
  6.     end
  7.   end
  8.   return total
  9. end
  10.  
  11. # O(1) + O(1) + O(n) * ( O(1) + O(1) + O(1) + O(1) + O(1) )
  12. # O(1) + O(1) + O(5n)
  13. # we only care about the largest term : 0(5n)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement