Question 1. For each function pair of frow(n) and fcolumn(n) in the following table, determine[1]the smallest positive integer n ≥ 2 that makes frow(n) ≥ fcolumn(n).
√
1000000logn
100000 n
10000n
1000nlogn
100n2
10n3
2n
1000000logn
√
-
-
-
-
-
-
-
100000 n
-
-
-
-
-
-
10000n
-
-
-
-
-
1000nlogn
-
-
-
-
100n2
-
-
-
10n3
-
-
2n
-
Question 2. For each function f(n) and time t in the following table, determine the largest input size n of a problem that can be solved in time t, assuming that the algorithm takes f(n) microseconds to solve the problem. Each input size n must be a positive number. (Note: 1 microsecond equals 10−6 second. For convenience, you may express n in the scientific notation, rounded to three decimal places, e.g. 1.234 × 108.) []
1 second
1 hour
1 year
1
Question 3. Please explain the following statements:
(i) Explain why the statement, “The running time of algorithm A is at least O(n2)”, does not make sense. Your explanation should include a detailed example.
(ii) We are given that an algorithm has complexity O(logn) in the given input size n. Explain why the complexity for this algorithm is also O(logb n), regardless of the choice of any base b 1 for the logarithm appearing in the expression.
Question 4. In every row of the table below, there are two functions f(n) and g(n) given.
Determine whether each of the three statements “f(n) = O(g(n))”, “f(n) = Ω(g(n))”, “f(n) = Θ(g(n))” is true or false for the given functions. You may indicate your answer as T/F in the
blanks provided in the table. ]
f(n)
g(n)
f(n) = O(g(n))
f(n) = Ω(g(n))
f(n) = Θ(g(n))
n1.01
nlogn
nlogn
logn!
1 + 1/2 + 1/3 + ... + 1/n
logn
n2n
3n
nπ
en
Question 5. Suppose f(n) and g(n) are real-valued functions in the single variable n, where n represents input size (assumed to be a positive integer). Are the following statements true or false? Please justify your answers with details.
(i) For any real constants a and b such that b 0, we must have (n + a)b = Θ(nb). (ii) f(n) + g(n) = Θ(min(f(n),g(n))).
(iii) f(n) = O(g(n)) implies g(n) = Ω(f(n)).
[1] You may find WolframAlpha (https://www.wolframalpha.com/input/?i=sqrt%28x%29+%3E10+*+log%28x% 29) useful to solve Question 1 and Question 2.
