HW6: Efficiency and Big-O Analysis

Goals

To get a better understanding of how to calculate the efficiency of algorithms—developing both your ability to work through calculations mathematically and your intuitive sense of estimating big-O. CourseNana.COM

Requirements

This is a solo assignment. This assignment is a problem set (no code to be handed in). You are welcome to talk with others about the problems, but you must write up your assignment by yourself, and you should not use any notes from talks with others while writing up your assignment. If you need notes, it likely means you still don't quite understand how to do the problem. Go back over your notes, ask more questions, or try to solve a similar problem on your own. Then come back a day or so later and try to write up your solution without your notes. CourseNana.COM

Submit a PDF file and Collaborations.txt to Blackboard. You have a few options for this: CourseNana.COM

1. Write it in a word processing program, then export or print it to PDF.
2. Write it by hand and scan it into a PDF. If you do this, please write neatly and clearly. Make sure to check that your scan is legible.
3. Write it in LaTeX and typeset it as a PDF. This has a little bit of a start up cost in terms of learning how to write math in LaTeX, but it makes it possible to write math clearly and quickly once you've learned it. If you go to grad school, you'll have to learn LaTeX eventually, and I'm happy to help you get started if you have questions (or ask on Piazza/search online). Overleaf is a good place to start.

Remember, the goal of your writeup is to communicate your understanding to us, so we can't accept writeups that we cannot read (either due to handwriting or file format issues). Extremely hard to read submissions will incur a loss of points. This assignment is worth 25 points. CourseNana.COM

Answer the following questions

Q1 [5 pts]

For each of the code snippets below, first answer how many times the output statement is printed. Your answer should be in terms of n$n$. Then, simply this expression, in big-O notation. CourseNana.COM

a. Snippet #1: CourseNana.COM

for (int i = 0; i < 2 * n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + " " + j);
    }
}

b. Snippet #2:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < 5; j++) {
        System.out.println(i + " " + j);
    }
}

c. Snippet #3:

for (int i = 0; i < n + 3; i++) {
    for (int j = n - 1; j >= 0; j--) {
        System.out.println(i + " " + j);
    }
}

d. Snippet #4:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (j == i) {
            System.out.println(i + " " + j);
        }
    }
}

e. Snippet #5:

for (int i = 0; i < 7*n; i++) {
    System.out.println(i);
}

for (int j = 0; j < n; j++) {
    System.out.println(j);
}

CourseNana.COM

Q2 [3 pts]

(Adapted from book exercise) Consider two programs, A and B. Program A requires 80n2+5n$80n^2+5n$ operations and program B requires 9n+50000$9n+50000$ operations. What is the big-O of each program? For which values of n$n$ will program A execute faster than program B? CourseNana.COM

Q3 [2 pts]

Suppose that you have an algorithm that iterates over an array of size n$n$ and performs an O(nlogn)$O(n\log n)$ operation on each iteration. What is the big-O of this algorithm? Explain your answer in one sentence, intuitively (i.e., you do not need to prove this using the definition of big-O). CourseNana.COM

Q4 [4 pts]

(Adapted from book exercise) Consider four programs—A, B, C, and D—that have the following performances: CourseNana.COM

• A is O(log(n))$O(\log (n))$
• B is O(n)$O(n)$
• C is O(n3)$O(n^3)$
• D is O(2n)$O(2^n)$

If each program requires 5 seconds to solve a problem of size 300, estimate the time required by each program for a problem of size 600. (Note: estimate as best you can with the information given—it isn't possible to know exactly how long the program would take, but this exercise is intended to give you a sense of the practical differences in timing for programs with different asymptotic efficiencies, aka., big-O functions.) CourseNana.COM

Q5 [5 pts]

(Adapted from book exercise) Find the tightest bound for each expression using the big-O notation, and show your proof (except for the third one). CourseNana.COM

a. 15n+30$\frac{1}{5}n+30$
b. 8n2+3n$8n^2+3n$
c. 7n3+2n$7n^3+2^n$ (no proof needed) CourseNana.COM

Q6 [2 pts]

Here are two claims that are false. For each claim, give functions f(n)$f(n)$ and g(n)$g(n)$ where the purported claim does not hold (i.e., give a counterexample). CourseNana.COM

a. Let h(n)=f(n)+g(n)$h(n)=f(n)+g(n)$. Then h(n)∈O(min(f(n),g(n)))$h(n)\in O(min(f(n),g(n)))$ 
b. Let h(n)=f(n)g(n)$h(n)=f(n)g(n)$. Then h(n)∈O(max(f(n),g(n)))$h(n)\in O(max(f(n),g(n)))$ CourseNana.COM

Q7 [4 pts]

In class, we talked about the efficiency of linear search versus binary search. The graphs below (please see the attached two graphs if they're not shown here) show timing data for searching using four different methods: 1) linear search on Java's built in ArrayList, 2) binary search on a sorted ArrayList, 3) search using the containsKey() method for Java's built in TreeMap (a map/dictionary implementation), and 4) search using the containsKey() method for Java's built in HashMap (a map/dictionary implementation). The top graph includes all four timings: green (Binary Search) and purple (HashMap Search) overlap with the red line (TreeMap Search). The bottom graph includes all but the linear search to make it easier to see differences. Each data point is the total time for 250,000 searches with a particular number of items n$n$ to search over. For example, a data point with its x-axis at 50,000 has 50,000 items the list, or 50,000 keys stored in the map. Using the two graphs and what you know about linear and binary search, give the tightest estimate you can for the big-O cost of a single search using each of the four types. Explain your answers in a few sentences. These graphs show some of the noisiness that can characterize real life timing measurements, but you should still be able to pick out trends in the timing data. Noise is especially likely to be evident in timing data where the total running time is small. CourseNana.COM

  CourseNana.COM