Skip to Main Content
Mastering Algorithms with C
book

Mastering Algorithms with C

by Kyle Loudon
August 1999
Intermediate to advanced content levelIntermediate to advanced
560 pages
18h 57m
English
O'Reilly Media, Inc.
Content preview from Mastering Algorithms with C

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 kn? 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). ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Introducing Algorithms in C: A Step by Step Guide to Algorithms in C

Introducing Algorithms in C: A Step by Step Guide to Algorithms in C

Luciano Manelli
Head First C

Head First C

David Griffiths, Dawn Griffiths

Publisher Resources

ISBN: 1565924533Supplemental ContentErrata Page