davidimoore / ruby_algorithm_examples Goto Github PK

##Asymptotic Notation

• Big 0 Notation - Represents the worst case scenario time required to accomplish a task
• Example counting the number of characters in a string
  • O(n) - Counting the characters one by one. The time it takes will change with n or t the length of the string
  • O(1) - Storing the string in a variable and calling a length method. The size of the string wouldn't affect the time. Only the time of the method length which is assumed to be a constant amount of time.
  • 0(n^2) - The time required increases exponentially
  • 0(log n) - Example binary search