Mastering Algorithms with C

Questions and Answers

Q: From lowest to highest, what is the correct order of the complexities O (n²), O (3ⁿ), O (2ⁿ), O (n² lg n), O (1), O (n lg n), O (n³), O (n!), O (lg n), O (n)?

A: From lowest to highest, the correct order of these complexities is O (1), O (lg n), O (n), O (n lg n), O (n ²), O (n ² lg n), O (n ³), O (2 ⁿ ), O (3n), O (n!).

Q: What are the complexities of T₁(n) = 3n lg n + lg n; T₂(n) = 2ⁿ + n³ + 25; and T₃(n, k) = k + n, where k ≤ n? From lowest to highest, what is the correct order of the resulting complexities?

A: Using the rules of O -notation, the complexities of T ₁, T ₂, and T ₃ respectively are O (n lg n), O (2 ⁿ ), and O (n). From lowest to highest, the correct order of these complexities is O (n), O (n lg n), and O (2 ⁿ ).

Q: Suppose we have written a procedure to add m square matrices of size n × n. If adding two square matrices requires O (n² ) running time, what is the complexity of this procedure in terms of m and n?

A: To add m matrices of size n × n, we must perform m - 1 additions, each requiring time O (n ²). Therefore, the overall running time of this procedure is:

O(m-1)O(n ²) = O(m)O(n ²) = O(mn ²)

Q: Suppose we have two algorithms to solve the same problem. One runs in time T₁ (n) = 400n, whereas the other runs in time T₂ (n) = n² . What are the complexities of these two algorithms? For what values of n might we consider using the algorithm with the higher complexity?

A: The complexity of T ₁ is O (n), and the complexity of T ₂ is O (n ²). However, the algorithm described by T ₁ involves such a large constant coefficient for n that when n < 400, the algorithm described by T ₂ would be preferable. This is a good example of why we sometimes consider other factors besides the complexity of an algorithm alone.

Q: How do we account for calls such as memcpy and malloc in analyzing real code? Although these calls often depend on the size of the data processed by an algorithm, they are really more of an implementation detail than part of an algorithm itself.

A: Usually calls such as memcpy and malloc are regarded as executing in a constant amount of time. Generally, they can be expected to execute very efficiently at the machine level regardless of how much data they are copying or allocating. Of course, their exact efficiency may depend on the computer on which they execute as well as other factors (particularly in the case of malloc, which depends on the state of the system at the moment it is called).