Question

3. Find the smallest positive integer k such that 1222+32++ n2 is big-O of nk. Explain.

Please show steps with explanations

Answer 1

Given that To find the smallest positive integer k. Here Given 1^2 + 2^2 + 3^2 + Ellipsis + n^2 = n(n + 1) (2n + 1)/6 = n(2n^2 + 2n + n + 1)/6 = 1n^3 + 3n^2 + n/6___(1) = 2n^3 + 3n^3 + n^3/6 (Because n^lessthanorequalto n^3 and n lessthanorequalto n^3) = 6n^3/6 = n^3 that their exists 1^2 + 2^2 + 3^2 + Ellipsis + n^2 lessthanorequalto n^3. Forall n elementof N. so, 1^2 + 2^2 + 3^2 + Ellipsis + n^2 is big - 0 of n^3. hence, For k = 3 We have 1^2 + 2^2 + 3^2 + Ellipsis + n^2 is big - 0 of n^k. \r\n Now We show that k is the least such that this is true. suppose k = 1 and 1^2 + 2^2 + 3^2 + Ellipsis + n^2 is big - 0 of n^k. then exist M > 0 such that 1^2 + 2^2 + 3^2 + Ellipsis + n^2 lessthanorequalto Mn. Forall n elementof N