szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 31 paź 2011, o 19:15 
Użytkownik

Posty: 75
Lokalizacja: Nowy Sącz
Udowodnić, że:
0,1n^2+10logn = O(n^2)
Definicja jest następująca: mówimy, że f(n)=O(g((n)), jeżeli istnieją dokładne stałe c i n_0, takie, że:
0  \le f(n)  \le c g(n)
Spełnione dla dowolnego: n  \ge n_0

Wiem, że funkcja kwadratowa rośnie szybciej niż logarytm, dlatego mogę napisać:
0,1n^2+10logn \le c n^2
0,1+\frac{10 \log{n}}{n^2} \le c

Dowód będzie prawdziwy, jeśli znajdę stałe c i n_0.

Jak mam to w takiej postaci jak najlepiej się za to zabrać? Liczenie granic?

Znalazłem stałą c=2 oraz n_0=10.

Jak je wstawie, otrzymuje prawdę. Więc w zasadzie wykazałem to, o co prosili w zadaniu?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 wykazać - suma współczynników Dwumianu Newtona = 2 do n-tej  Milva  4
 Wykzać poprawność równania  rafal_85  1
 Poprawność rozwiązania.  1608  1
 Podaj jawny wzór i udowodnij poprawność.  rafal_85  19
 Wykazać warunek na niezmiennik pętli  drago77  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl