Kako se određuje vremenska složenost operacija sa strukturom podataka Map?

U Androidu, struktura podataka Map obično se implementira putem HashMap ili TreeMap, a vremenska složenost operacija zavisi od konkretne implementacije:

• HashMap: operacije umetanja, pretraživanja i brisanja se u proseku obavljaju u O(1) — konstantno vreme, zahvaljujući heširanju. U najgorem slučaju (pri kolizijama), složenost može opasti na O(n).

• TreeMap: zasnovana na crveno-crnom stablu, pa se operacije umetanja, pretraživanja i brisanja obavljaju u O(log n).

Dakle, vremenska složenost operacija sa Map je određena korišćenom implementacijom i obično je ili O(1) (HashMap) ili O(log n) (TreeMap).