402 views
1 votes
1 votes
Analyze the runtime of the following piece of code. Give a bound using Θ notation.

function Pesky(n)

r ←0;

for i ←1 to n

do for j ←1 to i

do for k ← j to i+j

do r ←r + 1;

return r;

1 Answer

Best answer
1 votes
1 votes

for k ← j to i+j ===> k always run 'i' times ( if you didn't understand this let assume j=5 or any constant )

 

for j ←1 to i ===>

j=1 ==> k runs i times,

j=2 ==> k runs i times,

j=3 ==> k runs i times,

...

j=i ==> k runs i times,

therefore i+i+i+i+...+i (i times you are adding i ) ===>i2

 

for i ←1 to n ====> i runs upto 'n' times.

i=1 ===> 12

i=2 ===> 22

i=3 ===> 32

....

i=n ===> n2

 

therefore total = 12+22+32+....n2 = $\frac{(n)(n+1)(2n+1)}{6}$ = O(n3)

 

just see one time this question https://gateoverflow.in/228411/test-series-algorithms

selected by

Related questions

1 votes
1 votes
1 answer
1
AIkiran01 asked Jul 14, 2018
1,876 views
which of the following estimates are true? Explain with valid reasons.a) (2n)! is theta (n)!b) log((2n)!) is theta (log(n)!)
0 votes
0 votes
0 answers
2
debanjan sarkar asked Jan 12, 2019
441 views
Find a growth rate that cubes the run time when we double the input size. That is, if T(n) = X, then T(2n) = x^3.