Question

When counting the number of arithmetic operations in evaluating an expression, we often make the simplifying assumption that each operation has the same cost. For example, consider the following statement from the Merge-Sort algorithm for dividing the problem into two equal problems. q = ⌊(? + ?)/2⌋ we would say that the evaluation requires a total of 3 arithmetic operations (+, / and “floor”). That is, the time cost is 3. If that statement was embedded in a loop that executed 5 times, then we would say that the statement has a time cost of 5*3 = 15 arithmetic operations. Now consider this equation that was used in calculating the execution time for insertion sort. ∑ ? ? ?=2 = ?(?+1) 2 − 1 What is the difference in the time cost T(n) in terms of the number of arithmetic operations required to compute this formula depending on whether the algorithm is expressed based on the summation approach on the left-hand side of the equation or based on the closed formula approach on the right hand side of the equation as a function of the problem size n? You should express your analysis using the theta (Θ) notation.

Answer 1

For taking sum of j over j = 2 to n,

1. Using the right side formula, we get 4 operations, namely

n + 1,

n X (n + 1),

n X (n + 1) / 2,

and n * (n + 1) /2 - 1

Thus this equation is Theta(1) as we have constant number of operations for any n.

2. Using the loop at left side, we are calculating sum + j at every value from 2 to n,

Therefore it takes n - 1 steps to calculate.

Therefore the method is Theta(n).

The difference between the number of steps between the 2 methods is = (n - 1) - 4 = n - 5

This means that left side method takes n - 5 steps more than right side.

Hope this helps.

Please rate the answer if you like it.

Do leave a comment.Any suggestion/query is much appreciated.