For each fragment, find the running time T(n). For your analysis, make a table o
ID: 639750 • Letter: F
Question
For each fragment, find the running time T(n). For your analysis, make a table of the line, its cost, and number of times each line is executed. Type your answers. Be exact in your counts.
All of them don't have to be done, I just need some help when it comes to doing it. Please show the work that was done. Thank you!
1.
sum = 0;
for (i = 0; i < n; i++)
sum++;
2.
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
sum++;
3.
sum = 0;
for (i = 0; i < n; i++)
for (j = 0; j < n * n; j++) sum++;
4.
sum = 0;
for (i = 0; i < n; i++)
for(j = 0; j < i; j++)
sum++;
5.
sum = 0;
for (i = 0; i < n; i++)
for(j = 0; j < i * i; j++)
for(k = 0; k < j; k++)
sum++;
Explanation / Answer
1.
sum = 0; O(1)
for (i = 0; i < n; i++) O(N)
sum++; O(N-1)
T(n)=1+N+N-1
T(n)=O(N)
2.
sum = 0; O(1)
for (i = 0; i < n; i++) O(N)
for (j = 0; j < n; j++) N-1(N)
sum++; N-1*N-1
T(n)=1 + N + (N-1)N + N-1*N-1
T(n)=O(N^2)
3.
sum = 0; O(1)
for (i = 0; i < n; i++) O(N)
for (j = 0; j < n * n; j++) O(N-1)*(N^2)
sum++; O(N-1)*(N^2-1)
T(n)=1+N+(N-1)*(N^2) + O(N-1)*(N^2-1)
T(n)=O(N^3)
4.
sum = 0; O(1)
for (i = 0; i < n; i++) O(N)
for(j = 0; j < i; j++) O((N-1)N)/2
sum++; O(N-1)(N-1)/2
T(N)=1+N+(((N-1)N)/2)+O(N-1)(N-1)/2
T(N)=O(N^2)
5.
sum = 0;
for (i = 0; i < n; i++)
for(j = 0; j < i * i; j++)
for(k = 0; k < j; k++)
sum++;
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.