Note: In this homework set, log denotes the natural logarithm[1], i.e. the logarithm in base e.
Question 1. For each function pair of frow(n) and fcolumn(n) in the following table, determine[2]the smallest positive integer n ≥ 2 that makes frow(n) ≥ fcolumn(n). [5 points]
√
| 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.) [5 points]
| 1 second | 1 hour | 1 year | |
1
Question 3. Please explain the following statements:
- 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. [2 points]
- 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. [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)) |
| 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). [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]
[1] The 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”.
[2] 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.