- Write T(n) for the following algorithm. Explain how you calculated it. Indicat

Question

- Write T(n) for the following algorithm. Explain how you calculated it. Indicate whether the fragment execution time is O(n) or O(n2): for (int i = 0; i < n; i++) for (int j = n - 1; j >= i; j--) cout << i << " " << j << endl;

2- For the following T(n) find values of n0 and c such that cn3 is larger than T(n) for all n larger than n0. T(n) = n3 – 5n2 + 20n – 10

3- Write a program that compares the values of y1 and y2 in the following expressions for values of n from 0 to 100 in increments of 10. Does the result surprise you? y1 = 100 * n + 10 y2 = 5 * n * n + 2

Explanation / Answer

1)
for (int i = 0; i < n; i++)
for (int j = n - 1; j >= i; j--)
cout << i << " " << j << endl;
The execution time is O(n^2) as there is a nested loop.

2)
T(n) = n^3 – 5n^2 + 20n – 10

Let us take c = 1 and n0 = 4

T(n) = n^3 - 5(n^2-4n+2)

Let g(n) = n^2-4n+2

For n>4 g(n) is always positive. So T(n) < n^3

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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