3.1-3 Explain why the statement, “The running time of algorithm A is at \[O(n^2)\]
Solution: Let us assume the running time of the algorithm is T(n). Now, by definition, O-notation gives an upper bound for growth of functions but it doesn’t specifies the order of growth. Therefore, saying $$T(n) \ge O(n^2)$$ means growth of T(n) is greater than some upper bound which is meaningless as we do not have any idea about what we are comparing it with.
For example, $$f(n) = 0$$ is $$O(n^2)$$ for all n. So, $$T(n) \ge f(n)$$ doesn’t tell us anything new as all running times are non-negative.
Solution: Let us assume the running time of the algorithm is T(n). Now, by definition, O-notation gives an upper bound for growth of functions but it doesn’t specifies the order of growth. Therefore, saying $$T(n) \ge O(n^2)$$ means growth of T(n) is greater than some upper bound which is meaningless as we do not have any idea about what we are comparing it with.
For example, $$f(n) = 0$$ is $$O(n^2)$$ for all n. So, $$T(n) \ge f(n)$$ doesn’t tell us anything new as all running times are non-negative.
No comments :
Post a Comment