Kuidas hinnata TreeSet-i elementide lisamise operatsiooni ajakulutust?

Java keeles on TreeSet klass implementeeritud punase-musta puu alusel, mis on tasakaalustatud binaarne otsingupuu. Operatsiooni elementide lisamise ajakompleksus TreeSetis on O(log n), kus n on kogus olevate elementide arv.

See tuleneb sellest, et elemendi lisamisel otsitakse see esmalt puust, et määrata õige koht, ning seejärel tasakaalustatakse puu, mis võtab logaritmilise aega.

Näide:

TreeSet<Integer> set = new TreeSet<>();
set.add(10); // O(log n)
set.add(5);  // O(log n)
set.add(20); // O(log n)