Skip to Main Content
Java 6 Illuminated: An Active Learning Approach, 2nd Edition
book

Java 6 Illuminated: An Active Learning Approach, 2nd Edition

by Julie Anderson, Herve J. Franceschi
February 2008
Intermediate to advanced content levelIntermediate to advanced
1288 pages
39h 39m
English
Jones & Bartlett Learning
Content preview from Java 6 Illuminated: An Active Learning Approach, 2nd Edition
1130 CHAPTER 15 Running Time Analysis
Let’s compute the running time of powerOf2A as a function of the input n;
we will call it T1(n).
In the base case (n is equal to 0), powerOf2A makes only one comparison
and returns 1. Thus,
T1(0) = 1
Generally, since it takes T1(n) to compute and return powerOf2A(n), then
it takes T1(n – 1) to compute and return powerOf2A(n – 1).
Thus, in the general case, the comparison in the if statement will cost us
1 instruction; computing and returning powerOf2A(n – 1) will cost us
T1(n – 1); and multiplying that result by 2 will cost us 1 instruction. Thus,
the total time T1(n) can be expressed as follows:
T1(n) = 1 + T1(n
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

JFC Swing Tutorial, The: A Guide to Constructing GUIs, Second Edition

JFC Swing Tutorial, The: A Guide to Constructing GUIs, Second Edition

Kathy Walrath, Mary Campione, Alison Huml, Sharon Zakhour
Java Illuminated, 4th Edition

Java Illuminated, 4th Edition

Julie Anderson, Hervé J. Franceschi

Publisher Resources

ISBN: 9780763749637