2 votes 2 votes Algorithms gateforum-test-series algorithms time-complexity + – Gupta731 asked Jan 9, 2019 • edited Mar 12, 2019 by ajaysoni1924 Gupta731 587 views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply arvin commented Jan 9, 2019 reply Follow Share C? 0 votes 0 votes Gupta731 commented Jan 9, 2019 reply Follow Share Yes C is correct, please explain. 0 votes 0 votes arvin commented Jan 9, 2019 reply Follow Share n i^5 ≈ n^6 k=1 and log n^40 = 40logn and n^6 >> 40logn so x ≈ √ O(n^6) = O(n^3) = θ(n^3)= Ω(n^3) also X= O(n^3) or O(n^4) or O(n^c) ..... c>=3.... 1 votes 1 votes Gupta731 commented Jan 9, 2019 reply Follow Share I am getting it but why $\sum$$i^5$ $\approx$ $n^6$ 0 votes 0 votes arvin commented Jan 9, 2019 reply Follow Share since, ∑i^5= (1/6)n6 + (1/2)n5 + (5/12)n4 - (1/12)n2... 0 votes 0 votes Prateek Raghuvanshi commented Jan 9, 2019 reply Follow Share @ Gupta731 we can think like this - $\sum n ≈n^2$,$\sum n^2 ≈n^3$ ,$\sum n^3 ≈n^4$....$\sum n^5 ≈n^6$ 1 votes 1 votes Gupta731 commented Jan 9, 2019 reply Follow Share yeah got it..thanks 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Average bound will be n^3 and maximum upper bound can be n^6 Hence option “C” best suits rish1602 answered Jul 9, 2021 rish1602 comment Share Follow See all 0 reply Please log in or register to add a comment.