Questions and Answers
Q: From lowest to highest, what is the correct order of the complexities O (n2), O (3n), O (2n), O (n2 lg n), O (1), O (n lg n), O (n3), 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 2), O (n 2 lg n), O (n 3), O (2 n ), O (3n), O (n!).
Q: What are the complexities of T1(n) = 3n lg n + lg n; T2(n) = 2n + n3 + 25; and T3(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 1, T 2, and T 3 respectively are O (n lg n), O (2 n ), and O (n). From lowest to highest, the correct order of these complexities is O (n), O (n lg n), and O (2 n ).
Q: Suppose we have written a procedure to add m square matrices of size n × n. If adding two square matrices requires O (n2 ) 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 2). Therefore, the overall running time of this procedure is:
O(m-1)O(n 2) = O(m)O(n 2) = O(mn 2)
Q: Suppose we have two algorithms to solve the same problem. One runs in time T1 (n) = 400n, whereas the other runs in time T2 (n) = n2 . 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 1 is O (n), and the complexity of T 2 is O (n 2). ...