Consider the following two code segments:

 //Segment 1 //Segment 2 int sum = 0; int sum = 0; for (int i=1 ; i <= n; i++) for (int i=1 ; i <= n; i *= 2) for (int j=1; j = i; j *= 2 ) for (int j=1; j = i; j++ ) sum++; sum++; 

As you will observe, the two code segments are identical, except that the updating of variables i and j is swapped.

As in previous assignments, perform a careful micro-analysis of the time required for each of these code segments, using the following constants for the time it takes a machine to do specific operations:

A one assignment

B one evaluation of a Boolean (e.g., a comparison)

S one addition or subtraction

M one multiplication or division

P one increment (e.g., ++) [since the line w++ is largely equal to x = x + 1, P is roughly equal to A + S]

Evaluating the micro-analysis of the two code segments for large values of n, would you expect that execution of Segment 1 would take longer or shorter than Segment 2, or would the two code segments run in about the same time? Explain briefly.

Based on your micro-analysis, determine the Big- run-time for each segment. Is the Big- run-time the same for the two segments? Explain briefly.

Use your micro-analysis and the definition of Big-O to determine if the run-time for each code has O(n), O(n²), O(n³), O(n⁴), and O(n⁵). In each case, give a careful argument justifying your conclusions.