Udowodnić, że:
\(\displaystyle{ 0,1n^2+10logn = O(n^2)}\)
Definicja jest następująca: mówimy, że \(\displaystyle{ f(n)=O(g((n))}\), jeżeli istnieją dokładne stałe \(\displaystyle{ c}\) i \(\displaystyle{ n_0}\), takie, że:
\(\displaystyle{ 0 \le f(n) \le c g(n)}\)
Spełnione dla dowolnego: \(\displaystyle{ n \ge n_0}\)
Wiem, że funkcja kwadratowa rośnie szybciej niż logarytm, dlatego mogę napisać:
\(\displaystyle{ 0,1n^2+10logn \le c n^2}\)
\(\displaystyle{ 0,1+\frac{10 \log{n}}{n^2} \le c}\)
Dowód będzie prawdziwy, jeśli znajdę stałe \(\displaystyle{ c}\) i \(\displaystyle{ n_0}\).
Jak mam to w takiej postaci jak najlepiej się za to zabrać? Liczenie granic?
Znalazłem stałą \(\displaystyle{ c=2}\) oraz \(\displaystyle{ n_0=10}\).
Jak je wstawie, otrzymuje prawdę. Więc w zasadzie wykazałem to, o co prosili w zadaniu?