estw oti (1) nlogn < n^(2logn)  //sumbolismos: log_n sumenei logari8mos me bash n


logari8mizoyme thn  (1) me log_n
log_n(nlogn) < 2logn
log_n(n) + log_n(logn) < 2logn
1 +log_n(logn) < logn + logn (2)


h (2) mporei na bgei apo to a8roisma twn (3),(4)

1 < logn              (3)  isxuei afou gia n>1 (n = mege8os problimatos) logn>1
log_n(logn) < logn    (4)  isxuei


sthn arxh upo8esame oti h (1) isxuei.
Twra eimaste sigouroi oti h (1) isxuei afou oi (3),(4) oi opoies to a8roisma tous paragoun thn (1)


to katw fragma einai to nlogn. emeis exoume to  n^(2logn). diksame oti  nlogn < n^(2logn) ara *8woritika* mporoume na broume kalitero algori8mo
pou na prosegizei pio konta to nlogn