Algorithm, Big-Oh

A framework for Θ- simplifications: As a kind of reminder and reference, here are the basic rules for Θ-simplifications, where a, b stand for arbitrary terms, and n ≥ 1: (EQ) If a = b, then a = Θ(b). For example (n+5)^2 = θ(n^2 +10n+25). (IQ) If a≤b,then a=O(b). E.g.,2^n =O(3^n). (F) For a (constant!) factor α > 0, we have α · a = Θ(a). E.g., 5n^2 = Θ(n^2). (LO) Lower-order terms: if a = O(b), then a + b = Θ(b). E.g., n^2 + n^3 = Θ(n^3). (L1) logb(n) = Θ(lg(n)) for any (constant) b > 1. E.g., log10(n) = Θ(lg(n)). (L2) lg(n) = O(n^α) for any (constant) α > 0. E.g., lg(n) = O(n^2). (P)For(constant)α≥β>0,wehavenβ ≤ n^α. E.g., n^2 = O(n^3). (E) n^α = O(β^n) for any (constant) α > 0, β > 1. E.g., n^3 = O(2^n). Questions [login to view URL] Θ-expressions which are as simple as possible, and state the rules you applied: 4n^8 = Θ(?) 2n^6+8n^3+n^7 = Θ(?) 4·2^n+n^1000 = Θ(?) 5√n + log4(n) = Θ(?) (n+2)^4 = Θ(?) lg(n)+3^n+n^3 = Θ(?) 2. After Θ-simplifications one sees, that each of the following expression is either (asymp- totically) a logarithm (L), a power (P), or an exponential (E) — say which applies: (a) log10 n+5lgn (b) 1.6^n (c) 10n+n^2 (d)4 √n+logn (e) 2n/10^1000 + n^5 + lg n 3. Mark each of the following assertions “true” or “false”: (a) All logarithms are asymptotically equal. (b) Some exponentials are asymptotically smaller than some powers. (c) Every power is asymptotically smaller than every exponential. (d) Some powers are asymptotically smaller than some logarithms. (e) Every logarithm is asymptotically smaller than any power. (f) All powers are asymptotically equal. (g) All exponentials are asymptotically equal. 4. Solve the following recurrences, using the simplified Master Theorem, where you need to show the (small) computation, and state the case applied: (a) T (n) = 16T (n/2) + n^4 . (b) T(n) = 4T(n/2) + n^4. (c) T(n) = T(n/2) + T(n/2) + 2. (d) T(n) = 5T(n/3) + n. (e) T(n) = 7T(n/3) + n^2. (f) T(n) = 7T(n/7) + n^2.