Question

3. Given Pseudocode:

Algorithm2(n):

y = 0

for i = 10 to n + 10 do

for k = i to n + 10 do

y = y + k

return y

a. What's the output of Algorithm2(n) as a function of n?

b. What's the running time of Algorithm2(n) as a function of n?

c. Using Theta notation, describe the running time of Algorithm2(n) in the form of Θ(n^C) for some C.

d. Using Theta notation, describe the output of Algorithm2(n) in the form of Θ(n^C) for some C.

Answer 1

a) the output is as follows

y= y+k

it will do

[10+11+12+13+14+....+n+10] + [11+12+13+14+.....+n+10]+ [12+13+14+..+n+10] +...+n+10

which is

n/2[10+n+10] + (n-1)/2[11 + n+10] + (n-2)/2[12+n+10]+....+n+10 { becasue sum of AP is total terms/2[first term+last term}

this is the output in terms of n

b) the runtime complexity is

the k loops is runnning from i to n+10

and i is from 10 to n+10

so k going 10 to n+10

then 11 to n+10

then 12 to n+10

so number of iterations of k are

n+10-10 + n+10-11 +.....+n+10-n-10

which n+n-1+n-2+n-3+n-4+...+1

which is the sum of first n natural numbers which is equal to n(n+1)/2

c) since running time is n*(n+1)/2

we get time complexity is O(n*n) { because we neglect the constants and small terms}

d) we represented the output in solution a

we know in theta complexity we take only highest degree term and neglect the constants

so the output will be represented as O(n^2)

Hope you like the solution

please do thumbs up!