Try to accurately guess constants c and d , so that when you plot cn 2 and dn 2

Question

Try to accurately guess constants c and d , so that when you plot cn 2 and dn 2 on the same axis as your plot, they bracket your plot (i.e. one is above your plotted points, one below it) once n becomes large enough. Finally, work out how many steps your method to check that an array is sorted takes (i.e. estimate it's big-O) class. Compare this to how many steps your sorting method takes and c omment on the difference. Try to accurately guess constants c and d , so that when you plot cn 2 and dn 2 on the same axis as your plot, they bracket your plot (i.e. one is above your plotted points, one below it) once n becomes large enough. Finally, work out how many steps your method to check that an array is sorted takes (i.e. estimate it's big-O) class. Compare this to how many steps your sorting method takes and c omment on the difference.

Explanation / Answer

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C ) f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C ) f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C ) f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C ) => Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i ) f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C ) f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C ) => (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = (N / 2 - 1) * (N / 2) / 2 = ((N ^ 2 / 4) - (N / 2)) / 2 = (N ^ 2 / 8) - (N / 4) f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C ) f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C ) f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C ) f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2) f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2) f(N) = C * ( N ^ 2 / 4 ) + C * N f(N) = C * 1/4 * N ^ 2 + C * N

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.