1. 32 steps. They are:

1) i=0;

2) i<10?

3) ar[i]=i;

4) i++

5-31) steps 2-3-4 are repeated 9 more times

32) i<10?

Back...

2. 3n+2 steps. The sequence of steps 2-3-4 of question 1 is executed a total of n times. Back...

3. 4n+2 steps. The 3-step cycle is increased to 4 steps. Back...

4. 7n+2 steps. The 4-step cycle is increased to 7 steps (assuming each assignment is one step) Back...

5. (3n+2) + (3n+2) = 6n+4 steps. Basically, question 2 is executed twice in sequence. Back...

6. (c) Back...

7. 3n² + 4n + 2 steps. The inner-loop, which requires 3n+2 steps, is executed n times. In addition, the "i=0" is executed once, for each iteration of the inner loop the "i<n" and "i++" are executed once each, and the "i<n" is executed once after the final iteration. This yields: n * (3n+2) + 1 + 2n +1 = 3n²+2n+2n+2 = 3n²+4n+2. The Big-O value is O(n²), because the n² term dominates the value of this expression as n becomes large. Back...

8. yes, it will run faster. Back...

9. no, it is still O(n²). On the first iteration of the outer loop, the inner loop executes 0 times; one the second iteration it executes once, on the third iteration it executed twice, ..., on the i^th iteration it executes i-1 times, ..., on the n^th iteration it executes n-1 times. Total iterations are 1+2+3+...+(n-1), which is approximately n²/2, or 1/2 n², which is O(n²). Put another way, for each iteration of the outer loop (of which there are n), the inner loop iterates an average of n/2 times. Back...

10. Depends! What if value is found in first array element? (best case) In middle array element? (average case) Not found at all? (worst case). In most cases, we characterize by worst case. That is O(n). This is a sequential search. Back...

11. Again, consider worst case (not found). With each probe, interval size is cut in half. How many times can interval size be cut in half until it is 1?

After x probes (comparisons), interval size is y.

In worst case, algorithm continues until search space size is 1. Solve n/2^k = 1 for k, to get worst case number of comparisons. Back...

[ Lectures | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Peter Sanderson ( PeteSanderson@smsu.edu )