Time Complexity

overview

Summary

time_complexity describes how work grows with input_size. Use big_o to label the growth_rate. Remember the cases: worst_case, average_case, best_case. Common classes: constant_time (O(1)), logarithmic_time (O(log n)), linear_time (O(n)), linearithmic_time (O(n log n)), quadratic_time (O(n^2)), exponential_time (O(2^n)). Lower classes scale better as n grows. In Big O, keep the dominant_term and drop constants and lower_order_terms. Space matters too; see space_complexity.