Composing complexity classes

Normally, we need to find the total running time of complex operations and algorithms. It turns out that we can combine the complexity classes of simple operations to find the complexity class of more complex, combined operations. The goal is to analyze the combined statements in a function or method to understand the total time complexity of executing several operations. The simplest way to combine two complexity classes is to add them. This occurs when we have two sequential operations. For example, consider the two operations of inserting an element into a list and then sorting that list. Assuming that inserting an item occurs in O(n) time, and sorting in O(nlogn) time, then we can write the total time complexity as O(n + nlogn); that is, we bring the two functions inside the O(…), as per Big O computation. Considering only the highest-order term, the final worst-case complexity becomes O(nlogn).

If we repeat an operation, for example in...