## Question

Time Complexity

You can use the Java library method System.currentTimeMillis() to determine how long a program runs. Call the method at the beginning of your program and store the returned value. Call it again at the end of your program. Take the difference between the two values. That is the time (in milliseconds) that it took to execute your program.

In this assignment, you will create small sections of code. For each section of code, you will determine how long it takes to complete a given number of iterations. This will allow you to see the relationship between input size and execution time for the various loops. After entering data into each table, comment out the corresponding section of code and move on to the next problem. At the end, all of your loops will be in the program that you submit, but they will be commented out. Estimate how large n could be if you were to allow your program run for several hours. You may find it useful to use Excel to graph your results.

Afterward, answer the questions about space complexity.

1. Write a loop that has a time complexity of O(n) and label it clearly with a comment. In the body of the loop, slow down the loop by adding additional statements such as print statements or an inner loop with a constant number of iterations. Slow down the loop until input size of n=10 iterations requires approximately 200ms. Observe the growth in execution time relative to input size by determining how long it takes to complete the loop for various values of n (where n is the number of iterations). If execution exceeds 20 seconds, simply write “a long time.”

Value of n Execution time

10 Approximately 200ms

20

40

80

160

Based on the data you collected, give an estimate of what value of n would complete execution in 32,000 seconds (i.e. about 9 hours). _________________

After completing the table above, comment out your loop and move on to the next problem.

2. Write a loop that has a time complexity of O(n2) and label it clearly with a comment. In the body of the loop, slow down the loop by adding additional statements such as print statements or an inner loop with a constant number of iterations. Slow down the loop until input size of n=10 iterations requires approximately 200ms. Observe the growth in execution time relative to input size by determining how long it takes to complete the loop for various values of n (where n is the number of iterations). If execution exceeds 20 seconds, simply write “a long time.”

Value of n Execution time

10 Approximately 200ms

20

40

80

160

Based on the data you collected, give an estimate of what value of n would complete execution in 32,000 seconds (i.e. about 9 hours). _________________

After completing the table above, comment out your loop and move on to the next problem.

3. Write a loop that has a time complexity of O(n3) and label it clearly with a comment. In the body of the loop, slow down the loop by adding additional statements such as print statements or an inner loop with a constant number of iterations. Slow down the loop until input size of n=10 iterations requires approximately 200ms. Observe the growth in execution time relative to input size by determining how long it takes to complete the loop for various values of n (where n is the number of iterations). If execution exceeds 20 seconds, simply write “a long time.”

Value of n Execution time

10 Approximately 200ms

20

40

80

160

Based on the data you collected, give an estimate of what value of n would complete execution in 32,000 seconds (i.e. about 9 hours). _________________

After completing the table above, comment out your loop and move on to the next problem.

4. Write a loop that has a time complexity of O(2n) and label it clearly with a comment. (Hint: Compute 2n and write a simple loop with that number of iterations.) In the body of the loop, slow down the loop by adding additional statements such as print statements or an inner loop with a constant number of iterations. Slow down the loop until input size of n=10 iterations requires approximately 200ms. Observe the growth in execution time relative to input size by determining how long it takes to complete the loop for various values of n (where n is the number of iterations). If execution exceeds 20 seconds, simply write “a long time.”

Value of n Execution time

10 Approximately 200ms

20

40

80

160

Based on the data you collected, give an estimate of what value of n would complete execution in 32,000 seconds (i.e. about 9 hours). _________________

After completing the table above, comment out your loop and move on to the next problem.

5. Write a loop that has a time complexity of O(n!) and label it clearly with a comment. (Hint: Compute n! and write a simple loop with that number of iterations.) In the body of the loop, slow down the loop by adding additional statements such as print statements or an inner loop with a constant number of iterations. Slow down the loop until input size of n=10 iterations requires approximately 200ms. Observe the growth in execution time relative to input size by determining how long it takes to complete the loop for various values of n (where n is the number of iterations). If execution exceeds 20 seconds, simply write “a long time.”

Value of n Execution time

10 Approximately 200ms

20

40

80

160

Based on the data you collected, give an estimate of what value of n would complete execution in 32,000 seconds (i.e. about 9 hours). _________________

After completing the table above, comment out your loop and move on to the next problem.

6. Consider the following loop that has a time complexity of O(log n):

for (int count = 1; count < n; count = count*2) {

System.out.println(count);

}

In the body of the loop, slow down the loop by adding additional statements such as print statements or an inner loop with a constant number of iterations. Slow down the loop until input size of n=10 iterations requires approximately 200ms. Observe the growth in execution time relative to input size by determining how long it takes to complete the loop for various values of n (where n is the number of iterations). If execution exceeds 20 seconds, simply write “a long time.”

Value of n Execution time

10 Approximately 200ms

20

40

80

160

Based on the data you collected, give an estimate of what value of n would complete execution in 32,000 seconds (i.e. about 9 hours). _________________

Space Complexity

1. If you have a size n one-dimensional array, how would you use Big-O notation to express the amount of space it requires as a function of n? _____________

2. Write a Java program with an array of ints as large as you can make it. How large can the array of ints be? ________________

3. If an int variable occupies 4 bytes, how much memory does the array occupy? _____________________

4. If you have a square (n x n) two-dimensional array, how would you use Big-O notation to express the amount of space required by the array as a function of n? ____________

5. Write a Java program and determine the size of the largest square two-dimensional array of ints you can create before running out of memory: ________________

6. If an int variable occupies 4 bytes, how much memory does the array occupy? _____________________

7. If you have a cubed (n x n x n) three-dimensional array, how would you use Big-O notation to express the amount of space required by the array as a function n? ______________

8. Write a Java program and determine the size of the largest cubed three-dimensional array of ints you can create before running out of memory: ________________

9. If an int variable occupies 4 bytes, how much memory does the array occupy? _____________________

Modern computers often have several gigabytes of RAM.

10. How much RAM does your computer have? ______________________

11. Based on the maximum array sizes you are able to allocate, approximately how much RAM does it appear you are able to use? __________________

12. Investigate: If there is a discrepancy between the physical memory on the computer and the memory you are able to use, why is that the case? Is there anything you could do to alleviate the discrepancy?

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

public class Analysis {/**

* @param args the command line arguments

*/

public static void main(String[] args) {

long start = 0;

long end = 0;

int n = 10;

// 1.

// This loops has time complexity of O(n). It has internal loop which

// bring the loop to run in around 200ms for n=10.

// n = 160;

// // Estimating current time

// start = System.currentTimeMillis();

// // Looping through the loop for given value of n

// for(int i=0; i<n; i++){

// // Internal loop to slow down the loop.

// for(long j=0; j< 60000000; j++){

// }

// }

// end = System.currentTimeMillis();

// System.out.println("Time Taken: " + (end-start) + " milliseconds");

// // 2.

// // This loops has time complexity of O(n^2). It has internal loop which

// // bring the loop to run in around 200ms for n=10.

// n = 160;

// // Getting current time.

// start = System.currentTimeMillis();

// // Looping through the n*n number of iterations

// for(int i=0; i<n*n; i++){

// // Iternal loop to slow is down for n=10. It will run

// // in approx 200ms.

// for(long j=0; j< 5500000; j++){

// }

// }

// // Getting final time after the loops.

// end = System.currentTimeMillis();

// // Printing the time difference

// System.out.println("Time Taken: " + (end-start) + " milliseconds");

// // 3.

// // This loops has time complexity of O(n^3). It has internal loop which

// // bring the loop to run in around 200ms for n=10.

// n = 80;

// // Getting current time.

// start = System.currentTimeMillis();

// // Looping through the n*n*n number of iterations

// for(int i=0; i<n*n*n; i++){...

By purchasing this solution you'll be able to access the following files:

Solution.zip.