# Project #72993 - INFR 2820U: Algorithms & Data Structures

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
TutorRating
pallavi

Chat Now!

out of 1971 reviews
amosmm

Chat Now!

out of 766 reviews
PhyzKyd

Chat Now!

out of 1164 reviews
rajdeep77

Chat Now!

out of 721 reviews
sctys

Chat Now!

out of 1600 reviews
sharadgreen

Chat Now!

out of 770 reviews
topnotcher

Chat Now!

out of 766 reviews
XXXIAO

Chat Now!

out of 680 reviews
All Rights Reserved. Copyright by AceMyHW.com - Copyright Policy