Data structure question 1. Which of the following running times, T( n ), is not
ID: 3578888 • Letter: D
Question
Data structure question
1. Which of the following running times, T( n ), is not in O( n4 )?
2.
for (int i = 0; i <= 5; i++) {
linearTime( n );
}
linearTime( n );
linearTime( n );
linearTime( n );
3.
for (int i = 0; i <= n; i++) {
squaredTime( n );
}
linearTime( n );
squaredTime( n );
cubedTime( n );
4.
for (int j = 0; j <= n; j++) {
linearTime( n );
for (int i = 0; i <= n; i++) {
squaredTime( n );
}
linearTime( n );
}
d. O( n^8 )
5.
On a certain kind of computer, BubbleSort was repeatedly timed on problems of size 1024 (=210) and the average time over many executions was reportedly 1,000 seconds. What average time would you predict for problems of size 4096 (=212)?
a. 2^n - 1Explanation / Answer
1.
Ans: a, b, c are not in O(n^4)
a = O(2^n)
b = O(n)
c = O(n^3)
d = O(n^4)
2.
So, time complexity = 5*linearTime(n)
Total = 5xlinearTime(n) + 3xlinearTime(n)
T(n) = O(N)
Ans: a
3.
time complexity of for loo: n x squaredTime(n) = cubedTime(n)
Total time, T(n) = cubedTime(n) + linearTime(n) + squaredTime(n) + cubedTime(n)
= O(n^3)
Ans: a
4.
time complexity of for loop: n x ( linearTime(n) + n x squaredTime(n))
= n x ( O(n) + O(n^3))
= O(n^4)
Total complexity = O(n^4) + linearTime(n)
T(n) = O(n^4)
ANS: a
5.
Time complexity of bubblesort = n^2
So, for problem size 1024, time taken = 1000
So, for problem size 4096 = 4 x 1024
= (4 x n)^2 = 16 x n^2
= 16 x 1000 = 16000
Ans: a
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.