Chapter 2, Problem 10E

Program Plan Intro

Computational complexity:

• The resource used by an algorithm is known as its complexity.
• The resources required for solving computational problems or for executing an algorithm.
  • Time complexity denotes the complexity expressed in terms of execution time.
  • Space complexity denotes the complexity expressed in terms of memory needed for computation.
  • Complexity of operations that is mathematical.

Explanation of Solution

(b) The auto increment “cnt2++” is executed exactly “n²” times

• The external for loop is executing “n” times
• The internal for loop is executin...

Explanation of Solution

(c) The auto increment “cnt3++” is executed exactly “nlogn” times

• The external for loop is executing “logn” times
• The internal for loop is executing “n” times

$\begin{array}{l}n*{\displaystyle {\sum }_{i=1}^{logn}i}=1+2+3+\mathrm{...}logn\\ =n\end{array}$

Explanation of Solution

(d) The auto increment “cnt4++” is executed exactly “n” times

• The external for loop is executing “logn” times
• The internal for loop is executing “2ⁿ” times

$\begin{array}{l}{\displaystyle {\sum }_{i=1}^{\log n}{2}^i}=2+2^2+2^3+\mathrm{...}{2}^{\log n}\\ =2\frac{(2^{logn}}{}\end{array}$