Western Governors University (WGU) ICSC2100 C949 Data Structures and Algorithms I Practice Exam

The type of function that becomes very expensive very quickly, especially as the size of the input data increases, is the one described by O(n^2). This notation indicates that the time complexity grows quadratically in relation to the size of the input, n.

When you analyze algorithms that fall into this category, you will find that they typically involve nested iterations over the data. For example, consider a simple sorting algorithm like bubble sort, which compares each element with every other element. As the size of the input list increases, the number of comparisons grows significantly, resulting in performance that deteriorates rapidly for larger datasets. This behavior can limit the practicality of using such algorithms on large inputs compared to those with lower time complexities, making O(n^2) functions particularly costly in terms of time efficiency.

In contrast, other complexities such as O(n) scale linearly and O(log n) scale logarithmically, both of which grow much more slowly as n increases. O(nm), representing a function that depends on two different dimensions which could lead to more complexity, still does not reflect the rapid growth of O(n^2) with respect to a single variable input size. Thus, O(n^2) is considered to escalate in cost