Ho seguito l'esercizio:
An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in 1 min if the running time is the following:
- linear
- O (N log N)
...
Quindi l'algoritmo può elaborare 100 elementi in 0,5 ms, quindi 100 * (2 * 1000 * 60) = 12 000 000 elementi elaborati per il tempo lineare.
Ora come risolvere 12 000 000 = O (N log N) per N? N = 2 ^ (12 000 000 / N)
E sono bloccato su come eliminare l'esponenziale N.
Anche l'esercizio continua:
- Order the following functions by growth rate, and indicate which, if any, grow at the same rate.:
N, square root of N, N^1.5, N^2 , N log N, N log log N, N log^2 N, N log (N^2), 2/N, 2N, 2N/2, 37,N^3, N^2 log N
Poiché non ho alcuna soluzione come riferimento qui è mio:
2/N < sqrt(N) < 37< N=2N/2 < 2N < N log log N < N log N < N log (N^2) < N log^2 (N) < N^1.5 < N^2 < N^2 log N
Sarebbe bello se qualcuno potesse guardarlo e correggermi dove potrei sbagliarmi.