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 ²). ...