logo

Assignment | The marked areas and submit using the Gradescope system.

   

Added on  2022-08-12

3 Pages925 Words11 Views
Mandatory Exercise: Complexities
The 02105+02326 DTU Algorithms Team
Admin Write your solutions to the exercises directly in the marked areas and submit using the Gradescope system. Your
final submission should be a single pdf-file identical to the template but with your information and solutions filled in the
designated areas. Do not change or modify the template in any way. To produce the file we recommend that you print out
the document, fill it in by hand, and scan it. Make sure that your handwriting and scan is of good quality and easily readable.
Alternatively, you may use a pdf-editor to fill in the template directly. Asymptotic bounds should be as tight as possible.
Unless otherwise specified, the base of all logarithms is 2 and logk n means (logn)k. Refer to the homepage for the
collaboration policy and scoring requirement for the exam.
1 Complexities
1.1 For each statement below mark whether or not it is correct:
Y
es No 1 n3 + n2 logn+17· n2 =Θ(n3)
4
1017 +(n3)2 +log2 n = O(n5)
42logn+!n+ n1/3 =Ω(n1/3)
2logn + 3n03/320 +log10 n =Θ(n)
(3log2 n+55log(n10)+8logn)·logn =Ω(log10 n)
1.2 Arrange the following functions in increasing order according to asymptotic growth. That is, if g(n) immediately follows f
(n) in your list, it must hold that f (n)= O(g(n)).
8!n log(2n) 7n3 1n 3log2 n n4/2
Solution: 3log2 n, log(2n), 7n3, n4/2, 8√𝑛 , 1n
1.3 State the asymptotic running time in Θ-notation of each of the following algorithms.
Assignment | The marked areas and submit using the Gradescope system._1

End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents
The asymptotic behavior of this function f( n ) = 3n + 161 is.
|3
|479
|199

Sorting in place in linear time and Ranking of functions by asymptotic growth
|10
|1580
|328