Beginning Java Data Structures and Algorithms

Activity: Developing a Timing Table Using the Exponential Algorithm

Scenario

We have been asked to develop a timing table using an input size of 2, 10, 30, and 50 for an exponential algorithm of O(2ⁿ). Assume an operation time of 0.5 ms and that the algorithm only performs one operation.

Aim

To discover how badly exponential algorithms scale.

Steps for Completion

1. 0.5 x 2² = 2 ms
2. 0.5 x 2¹⁰ = 512 ms
3. 0.5 x 2³⁰ = 0.536 billion ms = 6.2 days
4. 0.5 x 2⁵⁰ = 5.629 and 10¹⁴ ms = 17838 years

Output

The results may be as follows:

Input Size (n)	Time : 1 Operations O(2n)
2	2 milliseconds
10	512 milliseconds
30	6.2 days
50	17838 years

Table 1.4: Timings for the O(2ⁿ) algorithm

In this section, we have compared different types of algorithmic ...