Q.1: Complete the following: a. F(n)=12n 5 +4n 3 is O(…………) b. F(n)= 5n 2 + 3n l
ID: 3821634 • Letter: Q
Question
Q.1: Complete the following:
a. F(n)=12n5+4n3 is O(…………)
b. F(n)= 5n2 + 3n log n + 2n 5 is O(…………)
c. F(n)= 3 log n + 2 is O(…………)
e. F(n)= 2n + 100 log n is O(…………)
Which function grows faster: …………………………..
Q.2: Prove the following:
a. 3n log n + 2n is (n log n) For n ……..
Q.3. Use the master method to give tight asymptotic bounds for the following recurrences.
a. T(n)= 2T(n/4) + 1.
b. T(n)= 2T(n/4) + n2.
Q. 4. Use Dijkstra’s algorithm to find the length of the shortest path between the vertices a and z in this weighted graph.
The shortest path is: ……………………………………………………..
10 Z 3 6 d e 8 c 1 4 2Explanation / Answer
HI, I have answered all parts of Q1.
Please repost ohter questions in separate post.
In Big-O notation, we generally ignore lower order terms and conastant terms.
Q.1: Complete the following:
a. F(n)=12n^5+ 4n^3
ignoring 4n^3 and 12 from 12n^5
O(n^5)
b. F(n)= 5n^2 + 3n log n + 2n^5
O(n^5)
c. F(n)= 3 log n + 2
O(logn)
e. F(n)= 2n + 100 log n
O(n)
Please let me know if you have any double in Q1
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.