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; Algorithms asymptotic-notation algorithms + – Rishav Kumar Singh asked Jul 26, 2018 Rishav Kumar Singh 402 views answer comment Share Follow See 1 comment See all 1 1 comment reply Rishav Kumar Singh commented Jul 27, 2018 reply Follow Share Sir, Now its enabled 0 votes 0 votes Please log in or register to add a comment.
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 Shaik Masthan answered Jul 26, 2018 selected Aug 1, 2018 by Rishav Kumar Singh Shaik Masthan comment Share Follow See all 2 Comments See all 2 2 Comments reply Shaik Masthan commented Jul 26, 2018 reply Follow Share i made a mistake on this, for k ← j to i+j ===> actually k always run 'i+1' times, then for j ←1 to i ===>i2+i times then for i ←1 to n ===> i=1 ===> 12 + 1 i=2 ===> 22 + 2 i=3 ===> 32 + 3 .... i=n ===> n2 + n therefore total = ( 12+22+32+....n2 )+ ( 1+2+3+...+n ) = $\frac{(n)(n+1)(2n+1)}{6} + \frac{n(n+1)}{2} $ = $\frac{(n)(n+1)(n+2)}{3}$ = O(n3) 2 votes 2 votes Rishav Kumar Singh commented Jul 27, 2018 reply Follow Share now i got it, thanks sir 0 votes 0 votes Please log in or register to add a comment.