1 votes 1 votes Consider $\sum_{i=0}^n{}$ i3 =x.what can be X 1.theta(n4) 2.theta(n5) 3.O(n5) 4.$\Omega$(n3) Algorithms asymptotic-notation multiple-selects + – A_i_$_h asked Oct 15, 2017 retagged Jul 8, 2022 by Lakshman Bhaiya A_i_$_h 374 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply saxena0612 commented Oct 15, 2017 reply Follow Share except 2 all seems to be correct to me. 0 votes 0 votes sourav. commented Oct 15, 2017 reply Follow Share correct $2$ is false rest are true 1 votes 1 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes 03 + 13 + 23 + . . .n3 = 1/4(n2(n+1)2) = 1/4 * n4 + some other terms Asymptotically <= n4, hence O(n5) is true. Therefore option 1 and option 4 is also true beside option 3 rishi71662data4 answered Oct 15, 2017 selected Oct 15, 2017 by sourav. rishi71662data4 comment Share Follow See all 3 Comments See all 3 3 Comments reply A_i_$_h commented Oct 15, 2017 reply Follow Share but 4 is the degree so it should be less that n4 O(n4) indicates worst case , which means it the worst possible so then how O(n5) is possible where am i going wrong 0 votes 0 votes rishi71662data4 commented Oct 15, 2017 reply Follow Share I may be wrong as well. What my understanding is, <= n5 is valid as well, as it will cover n4 0 votes 0 votes A_i_$_h commented Oct 15, 2017 reply Follow Share but suppose for quick sort what do we say we say worst case is O(n2) which means there is no way it can above that right? okok i got it theta value is n4 not O(n4) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes All Options are correct except Option 2. Ankit Srivastava 7 answered Oct 16, 2017 Ankit Srivastava 7 comment Share Follow See all 0 reply Please log in or register to add a comment.