# CMPT 280– Intermediate Data Structures and Algoirthms Assignment 2

\$35.00

Category:

## Description

Question 1 ():
For each of the following functions, give the tightest upper bound chosen from among the usual
simple functions listed in Section 3.5 of the course readings. Answers should be expressed in big-O
notation.
(a) (1 point) f1(n) = n log2
n + n
4
log280 n + 2
n
42
(b) (1 point) f3(n) = 0.4n
4 + n
2
log n
2 + log2
(2
n
)
(c) (1 point) f2(n) = 4n
0.7 + 29n log2
n + 280
Question 2 ():
Suppose the exact time required for an algorithm A in both the best and worst cases is given by the
function
TA(n) = 1
280n
2 + 42 log n + 12n
3 + 280√
n
(a) (2 points) For each of the following statements, indicate whether the statement istrue or false.
1. Algorithm A is O(log n)
2. Algoirthm A is O(n
2
)
3. Algoirthm A is O(n
3
)
4. Algoirthm A is O(2
n
)
(b) (1 point) What is the time complexity of algorithm A in big-Θ notation.
Question 3 ():
If possible, simplify the following expressions. Hint: See slide 11 of topic 4 of the lecture slides!
(a) (1 point) O(n
2
) + O(log n) + O(n log n)
(b) (1 point) O(2
n
) · O(n
2
)
(c) (1 point) 42O(n log n) + 18O(n
3
)
(d) (1 point) O(n
2
log2
n
2
) + O(m) (yes, that’s an ‘m’, not a typo; note that m is independent of n)
Question 4 ():
Consider the following Java code fragment:
// Print out all ordered pairs of numbers between 1 and n