O-Kalkül < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Beweise oder widerlege:
n [mm] \in O(\wurzel{n} [/mm] ) |
Hi,
Diese Aussage bedeutet ja das es eine Konstante c geben muss, so dass ab einem bestimmten [mm] n_0 [/mm] n [mm] \le \wurzel{n} [/mm] gelten muss. Das kann man graphisch ja leicht erkennen, dass das nicht sein kann, weil [mm] \wuzel{n} [/mm] sich asymptotisch immer einer Horizontalen nähert. Jedoch weiß ich nicht wie ich das richtig formal zeigen kann.
Gruß Snafu
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:46 So 18.04.2010 | | Autor: | felixf |
Moin Snafu!
> Beweise oder widerlege:
> n [mm]\in O(\wurzel{n}[/mm] )
>
> Diese Aussage bedeutet ja das es eine Konstante c geben
> muss, so dass ab einem bestimmten [mm]n_0[/mm] n [mm]\le \wurzel{n}[/mm]
> gelten muss.
Nicht ganz: es gibt da noch eine weitere Konstante $C > 0$, so dass fuer $n [mm] \ge n_0$ [/mm] gelten muss $n [mm] \le [/mm] C [mm] \sqrt{n}$.
[/mm]
> Das kann man graphisch ja leicht erkennen,
> dass das nicht sein kann, weil [mm]\wuzel{n}[/mm] sich asymptotisch
> immer einer Horizontalen nähert. Jedoch weiß ich nicht
> wie ich das richtig formal zeigen kann.
Teile die Gleichung durch [mm] $\sqrt{n}$ [/mm] und quadriere sie. Dann kannst du leicht ein $n$ angeben, welches [mm] $\ge n_0$ [/mm] ist und welches diese Ungleichung verletzt.
LG Felix
|
|
|
|
