Homework 14
CSSE 221 – Fundamentals of Software Development Honors
Fall 2008–2009

Recall the Due Dates and (from the syllabus) the Late (and early) Assignment Policy and guidelines for maintaining Academic Integrity.

Also recall that you can get help on any of these problems during the CSSE lab assistant hours, and you can use the Assignments Discussion Forum on Angel to discuss, clarify, or get help on these problems.

Things to do

1. Continue working on your CarsTrucksTrains project, using pair programming throughout (except for implementing the Truck and Train classes, which you should do separately). Strive to complete most of this project by the due date of this homework.
2. Do the written problems below.

Written problems

Write your answers to these questions. Turn your answers in via the appropriate Homework Drop Box on Angel.

1. Fill in the blank in the most appropriate way: 17m⁵ + 200m⁴ + 300 is O(____________).
2. Fill in the blank in the most appropriate way: 17r⁵ + 200r⁴ + 300 is O(____________).
3. Fill in the blank in the most appropriate way: 300³ is O(____________).
4. Fill in the blank in the most appropriate way: 40 2ⁿ is O(____________).
5. Fill in the blank in the most appropriate way: 40n log n is O(____________).
6. Fill in the blank in the most appropriate way: 40n log n² is O(____________).
7. Fill in the blank in the most appropriate way: 40n log² n is O(____________).
8. Which of the following is "smaller"? O(n³) or O(n^3.2)
9. Which of the following is "smaller"? O(n³) or O(2ⁿ)
10. Which of the following is "smaller"? O(n³) or O(n²log n)
11. What is the run-time of the following code snippet, in terms of n?

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

12. What is the run-time of the following code snippet, in terms of n?

    	for (int k = 0; k < n; ++k) {
    	    for (int j = 20; j < 143; ++j) {
    	        System.out.println("hello");
    	    }
    	}
    

13. What is the run-time of the following code snippet, in terms of n?

    	for (int k = 0; k < 200; ++k) {
    	    for (int j = 20; j < 143; ++j) {
    	        System.out.println("hello");
    	    }
    	}
    

14. What is the run-time of the following code snippet, in terms of n?

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

15. What is the run-time of the following code snippet, in terms of n?

    	for (int k = n/2; k < n * 4; ++k) {
    	    System.out.println("hello");
    	}
    

16. What is the run-time of the following code snippet, in terms of n?

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

17. What is the run-time of the following code snippet, in terms of n?

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

18. What is the run-time of the following code snippet, in terms of n?

    	for (int k = 0; k < n * n * n; ++k) {
    	    for (int j = 20; j < k; ++j) {
    	        System.out.println("hello");
    	    }
    	}
    

19. A block of code is characterized as O(n) and runs in 23 milliseconds on a certain input. From this information alone, what would you estimate as the runtime of the code if the size of the input were increased by a factor of 8?
20. A block of code is characterized as O(n²) and runs in 400 milliseconds on a certain input. From this information alone, what would you estimate as the runtime of the code if the size of the input were increased by a factor of 3?