Analyze the running times of the following algorithms. Express the running times

Question

Analyze the running times of the following algorithms. Express the running times in terms of the O() and Theta() notation, as appropriate. Determine in which cases the estimate Theta() cannot be used. Assume that n is a non-negative integer and that the running time of each algorithm is equal to the number of additions of numbers and assignment operations performed by this algorithm (a) fun(n) k = 0 for I = 1 to n: k = k + i return k (b) fun(n) k = 1 if n is even: for I = 1 to n: k = k + i return k (c) fun(n) if n

Explanation / Answer

1) Running Time complexity of fun(n) is O(n), as it is using one for loop.

2) Running Time complexity of fun(n)
   if n is odd it is O(1)
   if n is even it is O(n), as it is using for loop when n is even.

3)Running Time complexity of fun(n) can be written as
T(n) = T(n-1) + C which is O(n).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.