We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
If you run this you will get something like the png in the output directory which clearly shows that the loop is O(log(n)) whereas the equation is O(1).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Sherlock and Squares
You are viewing a single comment's thread. Return to all comments →
Again, that's not true. If you iterate, then the calculation will take longer as the difference between the inputs increases. If you use the equation it is independant of that difference and thus O(1). Consider this code I posted to github. https://github.com/SebastianCarroll/ruby-practice/blob/ff3e4a7bf0da93cdef54f972122fc3a5d86291f5/sherlock_and_squares/sherlock.rb
If you run this you will get something like the png in the output directory which clearly shows that the loop is O(log(n)) whereas the equation is O(1).