Witam, mam zadańko do egzaminu. Proszę o pomoc :)
Mamy algorytm który ma złożoność n^3, zwiększamy dwukrotnie dane wejściowe. Ile razy zwiększy się złożoność obliczeniowa przy większych danych.
No więc podstawiamy pod n = 2n
Mamy (2n)^3=8n^3
Widzimy że złożoność jest 8 razy większa.
I tu jest wszystko jasne, prosty jest również przykład gdzie wstępna złożoność to log n, wtedy jest ona o jakąś liczbę kroków większa. Problem pojawia się przy n log n. Przypuśćmy że rozmiar danych wejściowych również zwiększ się 2 razy. Rozpisując (2n log(n))/(n log(n)) możemy dojść do
(2 log(n) + 2)/log(n). Tego chyba nie da się dokładnie wyliczyć. Pozostaje chyba uznać za mało istotną to "wolną" dwójkę i zaokrąglić to do 2. Proszę o pomoc :)