Im folgenden sind jeweils zwei Folgen ´(f(n))_(n in NN)´ und ´(g(n))_(n in NN)´ vorgegeben. Gib mit kurzer Begründung an, welche der Beziehungen ´f(n) in O (g(n))´, ´f(n) in Omega (g(n))´ bzw. ´f(n) in Theta (g(n))´ jeweils gelten.

  1. ´f(n)= (23n^2 + 7n + 56)/(2n^2 + 3n + 1), g(n)=1´
  2. ´f(n) = (log_2(n + 2))^(log_2(n+1)), g(n) = 2n^4´
  3. ´f(n) = 2^n, g(n) = 2.0001^n´
Approach

  1. ´lim_(n -> oo) (23n^2 + 7n + 56)/(2n^2 + 3n + 1) = 23/2 = 11.5´

    => ´f(n) in O(g(n))´, ´f(n) in Omega(g(n))´ und ´f(n) in Theta(g(n))´

  2. ´f(n) in Omega(g(n))´ da ´f(n)´ durch ´n´ im Exponenten auf lange Sicht schneller wächst als eine Konstante im Exponenten.

  3. ´f(n) !in Theta(g(n))´, ´f(n) in O(g(n))´ und ´f(n) !in Omega(g(n))´ da es kein c gibt, so dass ´EE n_0 in NN: AA n >= n_0: c <= (f(n))/(g(n))´


Solution
      • ´f(n) in O(g(n))´
      • ´f(n) in Omega(g(n))´
      • ´f(n) in Theta(g(n))´
      • ´f(n) in Omega(g(n))´
      • ´f(n) !in Theta(g(n))´
      • ´f(n) in O(g(n))´
      • ´f(n) !in Omega(g(n))´
  • URL:
  • Language:
  • Subjects: math
  • Type: Explain
  • Duration: 25min
  • Credits: 3
  • Difficulty: 0.6
  • Tags: hpi big O
  • Note:
    HPI, 2014-04-14, Mathe 2, Aufgabe 12
  • Created By: adius
  • Created At:
    2014-07-26 08:16:25 UTC
  • Last Modified:
    2014-07-26 08:16:25 UTC