obere laufzeitschranke zu beweisen.
O(8^(n)) = 3^(O(n))
in worten: O von acht hoch n ist gleich 3 hoch O von n
was bedeutet diese aussage und wie kann man sie beweisen.
ich habs mit der definition von O versucht mit f(n) = O(n) .... f(n) <= c * g(n), aber bin nicht weiter gekommen.
definition der o notation:
f(n) = Ο(g(n))
∃n0 ∈ N ∧ c > 0, ∀n ≥ n0: |f(n)| ≤ c * g(n)
danke,
skull
O(8^(n)) = 3^(O(n))
in worten: O von acht hoch n ist gleich 3 hoch O von n
was bedeutet diese aussage und wie kann man sie beweisen.
ich habs mit der definition von O versucht mit f(n) = O(n) .... f(n) <= c * g(n), aber bin nicht weiter gekommen.
definition der o notation:
f(n) = Ο(g(n))
∃n0 ∈ N ∧ c > 0, ∀n ≥ n0: |f(n)| ≤ c * g(n)
danke,
skull
