Question

Question 4.5 Consider the fragment in Algorithm 4.8 shown below.
Algorithm 4.8

sum = 0;
for (i =1; i <=f(n); i ++)
sum += i;

Here f(n) is a function call. Give a simple and tight Big-Oh upper bound on the
running time of Algorithm 4.8, as a function of n, on the assumption that

(a) the running time of f(n) is O(n), and the value of f(n) is n!.
(b) the running time of f(n) is O(n), and the value of f(n) is n.
(c) the running time of f(n) is O(n²), and the value of f(n) is n.
(d) the running time of f(n) is O(1), and the value of f(n) is 0.

Answer 1

(a)
the running time of f(n) is O(n), and the value of f(n) is n!.
tight Big-Oh upper bound on the running time of Algorithm 4.8 is O(n!)

(b)
the running time of f(n) is O(n), and the value of f(n) is n.
tight Big-Oh upper bound on the running time of Algorithm 4.8 is O(n)

(c)
the running time of f(n) is O(n2), and the value of f(n) is n.
tight Big-Oh upper bound on the running time of Algorithm 4.8 is O(n^2)

(d)
the running time of f(n) is O(1), and the value of f(n) is 0.
tight Big-Oh upper bound on the running time of Algorithm 4.8 is O(1)