Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def count_ones(a_list)
- total = 0 # O(1) + O(1) -- constant store + constant fetch for object '0'
- a_list.each do |e| # O(n) -- because it increases linearly with input
- if e == 1 # O(1) -- because binary operations are constants
- total += 1 # O(1) + O(1) + O(1) + O(1) -- constant fetch, constant fetch, binary operation (+), constant store
- end
- end
- return total
- end
- # O(1) + O(1) + O(n) * ( O(1) + O(1) + O(1) + O(1) + O(1) )
- # O(1) + O(1) + O(5n)
- # we only care about the largest term : 0(5n)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement