HW9: Efficiency and Asymptotic Complexity

Answer the following questions:

1. (Book exercise 4.12) Suppose that your implementation of a particular algorithm appears in Java as follows:

   for(int pass = 1; pass <= n; pass++) {
       for(int index = 0; index < n; index++) {
           for(int count = 1; count < 10; count++) {
               ....
           }
       }
   }
   

   The algorithm involves an array of $n$ items. The previous code shows the only repetition in the algorithm, but it does not show the computations that occur within the loops. These computations, however, are independent of $n$ (in other words, they are “constant-time” operations). What is the asymptotic order of the algorithm?

2. (Book exercise 4.17) Consider four programs — A, B, C, and D — that have the following performances:
   • A is $O(\log(n))$
   • B is $O(n)$
   • C is $O(n^2)$
   • D is $O(2^n)$
   If each program requires 10 seconds to solve a problem of size 1000, estimate the time required by each program for a problem of size 2000.
3. (Book exercise 4.18) Suppose that you have a list of strings that are not in sorted order. As a function of the number of strings, $n$, what is the time complexity of searching for a particular word in this list? (We're assuming here that string comparisons are constant-time operations.)
4. (Adapted from book exercise 4.4) Using the definition of big O, demonstrate that:
   1. $6 n^2 + 3$ is $O(n^2)$.
   2. $n^2 + 17 n + 1$ is $O(n^2)$.
   3. $5 n^3 + 100 n^2 - n - 10$ is $O(n^3)$.
   4. $3 n^2 + 2^n$ is $O(2^n)$.
   5. $2 n \log_2(n) + 4 n$ is $O(n \log(n))$.
   6. $n + 4 \log_2(n)$ is $O(n)$.
5. (Adapted from book exercise 4.9) Demonstrate that:
   1. $7 n^2 + 5 n$ is not $O(n)$.
   2. $3 n^3 + 8 n \log_2(n)$ is not $O(n \log(n))$.
6. Say you have two functions, $f$ and $g$. We say that $f(n)$ “asymptotically dominates” $g(n)$ if there exists some value for $n$ beyond which $f(n)$ is always less than (or equal to) $g(n)$. In other words, $f(n)$ dominates $g(n)$ if it is asymptotically “faster”. Using your knowledge of asymptotic order, predict which function asymptotically dominates the other, and write down your prediction as part of your answer. Once you've made your prediction, write me a proof to demonstrate that you are correct.
   1. $f(n) = 15 n + 10$, $g(n) = n^2 - 3 n$. Which one asymptotically dominates? Prove it.
   2. $f(n) = 3 n - 20$, $g(n) = 200 \log_2(n)$. Which one asymptotically dominates? Prove it.

(Book project 4.7, slightly altered) In mythology, the Hydra is a monster with many heads. Every time a hero chops off a head, two smaller heads grow in its place. Fortunately for the hero if the head is small enough, it does not grow back when chopped off. To kill the Hydra, all that the hero needs to do is to chop off all the heads.

Write a program that simulates the Hydra, in a class Hydra. Instead of heads, we will use strings. A stack of strings, then, represents the Hydra. Every time you pop a string from the stack, delete the first letter of the string and push two copies of the remaining string back onto the stack. For example, if you pop the string HYDRA, you then push two copies of the string YDRA to the bag. If you pop a one-letter word, don't push anything onto the stack; one-letter heads get completely destroyed. To begin the program, push a single word (passed in as a command-line argument) onto the empty stack. The Hydra dies when the stack is empty.

If you printed each “head” that you chopped off, then a sample run of the program might look like this:

> java Hydra ABC
Starting Hydra with "ABC"
Chopping head ABC
Chopping head BC
Chopping head C
Chopping head C
Chopping head BC
Chopping head C
Chopping head C
The Hydra is slain!

You'll need the following files for the Stack ADT:

• Stack.java
• MysteryStackImplementation.class

In your writeup, along with your answers to the exercises above, include your answers to the following questions:

1. Using big-O notation, predict the time requirement for this algorithm in terms of the number $n$ of characters in the initial string.
2. Time the actual execution of the program for various values of $n$, and write a chart with your results. (You don't need to create a plot; simply a series of $n$—time pairs will do.) For the timing, remove output statements from your program, as simply printing to the screen actually eats up a lot of time, and the program will take way too long on big $n$ values.