CS210 Lab: Libraries and Running Time Measurement Postlab Answers

Postlab Answers:

1. Modify the complexity.cpp code to find the running time for the following cases. Record the running time in milliseconds for:
1. O(n) a single "for" loop (Comment out one "for" loop)
2. O(1) an assignment statement (Comment out both "for" loops)
   

   Note: the running time will vary depending on the machine that you are using and how busy the CPU is. For both of these situations, you might get a runtime of zero. Of course, your runtime is not actually zero, but it might be a non-recordable length (smaller than milliseconds). You can slow down the run-time by including a "cout" statement into the original loop and changing n to smaller value such as 300 (otherwise, it will take too long).

2. What would you expect to happen with the run-time? Does this occur?

I would expect that the run-time follows the following pattern:

runtime_of_O(n²)_function > runtime_of_O(n)_function > runtime_of_O(1)_function
	

This did happen. But I also expected

runtime_of_O(n)_function=sqrt(runtime_of_O(n²)_function); where, sqrt represents the square root

This didn't happen. However, you can say that a function "is big O n squared", but you can not say that a function "equals big O of n squared". O is not a mathematical function, therefore, most mathematical properties will not apply.