O-Notation Beispiele und Fragen

09.03.2020, 18:38	KonverDiv	Auf diesen Beitrag antworten »
O-Notation Beispiele und Fragen Guten Abend, Ich habe von einer amerikanischen Uni ein interessantes Aufgabenblatt gefunden, wo es um die O-Notation geht. Es ist dort folgendes zu bestimmen: Prüfe ob $\begin{eqnarray} f = O(g) \end{eqnarray}$ , oder $\begin{eqnarray} f = \Omega(g) \end{eqnarray}$ oder beides, in diesem Fall $\begin{eqnarray} f = \Theta(g) \end{eqnarray}$ gilt Mich interessieren hier drei Aufgaben im Detail, diese lauten: 1.) $\begin{eqnarray} f(n) = 2^{k\cdot \log(n)}, g(n) = n^k \end{eqnarray}$ 2.) $\begin{eqnarray} f(n) = 2^n, g(n) = 2^{2n} \end{eqnarray}$ 3.) $\begin{eqnarray} f(n) = n^{1.01}, g(n) = n \cdot \log^2(n) \end{eqnarray}$ Zu 1.) und 3.) habe ich keinen Ansatz, bei 2.) würde ich behaupten: $\begin{eqnarray} 2^{2n} = (2^2)^n = 4^n \end{eqnarray}$ damit wäre dann $\begin{eqnarray} 4^n \end{eqnarray}$ eine Obere Schranke zu $\begin{eqnarray} 2^n \end{eqnarray}$ womit dann $\begin{eqnarray} f = O(g) \end{eqnarray}$ wäre (da 4 größer als 2). Ich würde mich sehr freuen, wenn mir Jemand weiterhelfen könnte!
11.03.2020, 20:34	Cugu	Auf diesen Beitrag antworten »
1.) Umformen mittels Logarithmusgesetzen und dann fast analog zu 2.) 3.) Potenz gegen Logarithmus wie üblich mit L'Hôpital's rule

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »