(Solved): Consider the following algorithm segment. Assume that n is a positive integer. for i:= 1 ton for j ...
Consider the following algorithm segment. Assume that n is a positive integer. for i:= 1 ton for j := [(1 + 1)/2] to n X:=1.j next j next i (a) What is the actual number of elementary operations (additions, subtractions, multiplications, divisions, and comparisons) that are performed when the algorithm segment is executed? For simplicity, count only comparisons that occur within if-then statements, and ignore those implied by for-next loops. Express your answer in terms of n. (Hint: See Example 11.3.4 and Exercise 11.3.17a in the "Read It" link.) For odd n the number of operations is For even n the number of operations is (b) Apply the theorem on polynomial orders to the expressions in part (a) to find that an order for the algorithm segment is n