0 Daumen
1,9k Aufrufe

Ich bräuchte Hilfe bei diesem Beweis. Habe angefande l'hospital zu nehmen für den ersten Teil und hatte auch einen exakten Grenzwert ( für log2 in log 10 hatte ich 1/log2 und für log10 in log 2  als ergebnis log 2). Reicht es einen Grenzwer zu haben um damit zu argumentieren dass ist in dieser ensprechenden Lauzeit drin ist?

Für den zweiten Teil habe ich noch keine gescheite Idee. Außer dass 10^n größer als 2^n ist aber weiß da auch nicht wie ich das formal aufschreiben kann.

blob.png

Avatar von

1 Antwort

+1 Daumen

Sag mal, kennst Du eigentlich die Definition von \(f(n)\in{\mathcal O}(g(n))\)? Es soll eine Konstante \(C\) geben, sodass \(f(n)\le Cg(n)\) fuer fast alle \(n\) gilt.

Nun unterscheiden sich bekanntlich Logarithmen zu verschiedenen Basen nur um einen konstanten Faktor, d.h. es gibt sogar ein \(C\) mit \(\log_2n=C\log_{10}n\) fuer alle \(n\). Also \(\log_2n\in{\mathcal O}(\log_{10}n)\) und ganz analog \(\log_{10}n\in{\mathcal O}(\log_2n)\).

Zum zweiten Teil: Wenn \(10^n\in{\mathcal O}(2^n)\) sein sollte, dann muesste es ein \(C\) mit \(10^n\le C\cdot2^n\) fuer fast alle \(n\) geben. Das bedeutet aber \(5^n\le C\) fuer fast alle \(n\). Ein solchges \(C\) kann es nicht geben, denn \(5^n\) ist unbeschraenkt.

Avatar von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community