Description
Question 1. For each function pair of frow(n) and fcolumn(n) in the following table, determine2
the smallest positive integer n ≥ 2 that makes frow(n) ≥ fcolumn(n). [5 points]
1000000 log n 100000√
n 10000n 1000n log n 100n
2 10n
3 2
n
1000000 log n – – – – – – –
100000√
n – – – – – –
10000n – – – – –
1000n log n – – – –
100n
2
– – –
10n
3
– –
2
n
–
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
.) [5 points]
1 second 1 hour 1 year
log n
√
n
n
n log n
n
2
n
3
2
n
n!
1The logarithm notation is not consistently used throughout various academic disciplines, so what “log” (with
no subscript) means would depend on the context. For example, in mathematics (especially in functional analysis
and analysis-related areas), log by default is natural logarithm. In information theory, log is commonly used to
denote base 2 logarithm. In some engineering areas (e.g. communication theory), log is sometimes in base 10,
but sometimes in base 2. More theoretical engineering papers would use log to mean natural logarithm. The
common good practice in research papers is to specify which base is being used in logarithms, since there is
actually no “universally accepted convention”.
2You may find WolframAlpha (https://www.wolframalpha.com/input/?i=sqrt%28x%29+%3E10+*+log%28x%
29) useful to solve Question 1 and Question 2.
1
Question 3. Please explain the following statements:
(i) Explain why the statement, “The running time of algorithm A is at least O(n
2
)”, does
not make sense. Your explanation should include a detailed example. [2 points]
(ii) We are given that an algorithm has complexity O(log n) 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. [3 points]
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. [5 points]
f(n) g(n) f(n) = O(g(n)) f(n) = Ω(g(n)) f(n) = Θ(g(n))
n
1.01 n log n
n log n log n!
1 + 1/2 + 1/3 + … + 1/n log n
n2
n 3
n
n
π
e
n
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 = Θ(n
b
). [3 points]
(ii) f(n) + g(n) = Θ(min(f(n), g(n))). [1 point]
(iii) f(n) = O(g(n)) implies g(n) = Ω(f(n)). [1 point]
2
