f in O aus(g(n) || Theta || Omega ?

Question

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!

Answer 1

f(n) = ⌊log10(n)⌋  und g(n) = ⌊log2(n)⌋

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

Es ist log₂(n) = log₁₀(n)/log₁₀(2) (Basisumrechnung).

Also ist log₁₀(n) / log₂(n) = log₁₀(2) unabhängig von n.

Damit ist schon mal log₁₀(n) ∈ Θ(log₂(n)).

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