Question

Determine the efficiency and big-O notation for the following algorithm:

The algorithm processes an input with the size of 4096 in the run-time of 512 milliseconds; The algorithm processes an input with the size of 16,384, with the run-time of 8192 milliseconds (4pts).

Answer 1

Answer and Explanation:

To calculate Big O, go through each line of code and determine O(!), O(n) and return your calculation.

For example,

In O (5 +6n), where 6 5 represent five instances of O(1), and 6 represent the 6 O(n).

We compute the time complexity of the algorithm. We get the result, just an estimation. In given algorithms, run time in milliseconds has been provided, such as in T (1) algorithm process in 512 milliseconds and T(2) algorithms process 8129 milliseconds. But big O notation not measured in milliseconds. Information given is not enough to calculate the big O notation.