INFR 2820U: Algorithms & Data Structures

Assignment 1

Exercise V ( 60 points) For each of the following five program fragments:

a. Computing the theoretical time complexity: Count the number of multiplication as basic operation, and state the Big-Oh for each complexity. Prove only how did you get the big-Oh only for part 1*.*

b. Computing the actual running times: Implement the code in the language of your choice, and find the running time for several values of *n.* Plot results in a graph.

c. Compare the theoretical time complexity with the actual running times. Do you see any relationship between the two?

1.

NegativeSumSquare = 0;

for (i = 1; i <= n; i++)

Sum = Sum – i*i;

2.

Negative3SumSquare = 0;

for (i = 1; i <= 3*n; i++)

Negative3Sum = Negative3Sum – i*i;

3.

NegativeSubSumSquare = 0;

for (i = 1; i <= n; i++)

for (j = 1; j <= i; j++)

NegativeSubSum = NegativeSubSum – j*j;

Exercise VI: (20 points) Put the following recurrence relations into closed forms:

a. T(n) = T(n-1) +3

T(1) = 9

b. T(n) = T(n-1) + n

T(1) = 3

Exercise VII: (20 points) Use the Master Method to find the approximate solution for the following recurrence relations. Be sure to identify the values of *a, b, *and *d* in your answer.

a. T(n) = 2 * T(n/2) + n -3

b. T(n) = 4 * T(n/7) + n2 + 4

c. T(n) = 3 * T(n/5) + n3 –n+ 2

*Project does not have any attached files*

Subject | Computer |

Due By (Pacific Time) | 06/05/2015 04:00 am |

Tutor | Rating |
---|---|

pallavi Chat Now! |
out of 1971 reviews More.. |

amosmm Chat Now! |
out of 766 reviews More.. |

PhyzKyd Chat Now! |
out of 1164 reviews More.. |

rajdeep77 Chat Now! |
out of 721 reviews More.. |

sctys Chat Now! |
out of 1600 reviews More.. |

sharadgreen Chat Now! |
out of 770 reviews More.. |

topnotcher Chat Now! |
out of 766 reviews More.. |

XXXIAO Chat Now! |
out of 680 reviews More.. |