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?

  3. 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.

Back to Exercise click here
Back to Libraries and Running Time Measurement Lab click here

CS Dept Home Page
CS Dept Class Files
CS210 Class Files

Copyright: Department of Computer Science, University of Regina.