1 votes 1 votes Is there Any short cut to do these questions fast ? Algorithms time-complexity test-series + – Prince Sindhiya asked Oct 23, 2018 • retagged Jul 16, 2022 by Anjana5051 Prince Sindhiya 694 views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply Utkarsh Joshi commented Oct 23, 2018 i edited by Utkarsh Joshi Oct 24, 2018 reply Follow Share when i=1, j<=1, statement will be executed for 1 time when i=2, j<=4, the statement will be executed for 4 time when i=3, j<=9,statement will be executed 9 times So 1+4+9+16+..... sum of first n squares= n*(n+1)*(2n+1)/6 = O(n^3) 0 votes 0 votes Prince Sindhiya commented Oct 23, 2018 i edited by Prince Sindhiya Oct 24, 2018 reply Follow Share @Utkarsh it is O(n^5) (edited) do it again 0 votes 0 votes Prince Sindhiya commented Oct 23, 2018 reply Follow Share You forgot about 3 for loop 0 votes 0 votes Hemanth_13 commented Oct 23, 2018 i edited by Hemanth_13 Oct 23, 2018 reply Follow Share Prince Sindhiya Could you please explain how ? I'm missing somewhere 0 votes 0 votes Utkarsh Joshi commented Oct 23, 2018 i edited by Utkarsh Joshi Oct 24, 2018 reply Follow Share Idk what I forgot but according to me it would be n^3 only 0 votes 0 votes Somoshree Datta 5 commented Oct 24, 2018 i edited by Somoshree Datta 5 Oct 24, 2018 reply Follow Share j executes for a total of 1+4+9+..+n2 times= n(n+1)(2n+1)/6. now for each value of j, k executes 1+2+3+..+j times. So when j executes n2 times, k executes for n2(n2+1)/2 times.. so time complexity is 1+(4*5/2)+(9*10/2)+..+(n2(n2+1)/2) = $\theta$(n5) Is this the right approach to follow? 0 votes 0 votes Hemanth_13 commented Oct 24, 2018 reply Follow Share so time complexity is 1+(4*5/2)+(9*10/2)+..+(n2(n2+1)/2) = θ(n5) How was it n^5 ? 0 votes 0 votes Somoshree Datta 5 commented Oct 24, 2018 reply Follow Share summation of 14+24+34+...+n4 is $\theta$(n5)..that is what i know 1 votes 1 votes Hemanth_13 commented Oct 24, 2018 reply Follow Share Thank you :) Got my error. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Answer would be O(n^5) Prince Sindhiya answered Oct 24, 2018 Prince Sindhiya comment Share Follow See all 2 Comments See all 2 2 Comments reply Utkarsh Joshi commented Oct 24, 2018 reply Follow Share I agree! it would be O(n^5) only! 0 votes 0 votes Utkarsh Joshi commented Oct 24, 2018 reply Follow Share which test series is this? 0 votes 0 votes Please log in or register to add a comment.