0 Daumen
406 Aufrufe

Hey leute,

ich komme bei dieser aufgabe nicht ganz so weiter, könnte mir da jemand bitte unter die Arme greifen ?

ich soll bestimmen ob f(n) in O(g) oder Ω oder Θ liegt.

Für 
f(n) = ⌊log10(n)⌋  und g(n) = ⌊log2(n)⌋  kann mir jemand erklären wie das geht ? Ich glaube das f in O(g(n)) liegt aber bei Theta würde ich ja beispielsweise erhalten :

c * ⌊log10(n)⌋  >= ⌊log2(n)⌋ --> wenn ich das dann aber durch f(n) teile damit c allein steht, würde man ja erhalten:
c >= ⌊log2(n)⌋ / ⌊log10(n)⌋  --> das kann ja nicht stimmen weil n gegen unendlich geht oder ?
Das heisst das Omega nicht sein kann und somit auch nicht Theta ? 
Sehe ich das richtig ? Und ist f(n) wirklich in O(g(n) enthalten ?
Vielen Dank im voraus!

von

1 Antwort

+1 Daumen
f(n) = ⌊log10(n)⌋  und g(n) = ⌊log2(n)⌋

f ∈ (O(g)) ⇔ ∃N∃c>0∀n>N |f(n)| < c·|g(n)|.

Es ist log2(n) = log10(n)/log10(2) (Basisumrechnung).

Also ist log10(n) / log2(n) = log10(2) unabhängig von n.

Damit ist schon mal log10(n) ∈ Θ(log2(n)).

Du musst noch herausfinden, ob sich durch die untere Gausklammer etwas ändert.

von 3,3 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community