Как се определя времевата сложност на операциите с структурата от данни Map?

В Android структурата от данни Map обикновено се реализира чрез HashMap или TreeMap, а времевата сложност на операциите зависи от конкретната реализация:

• HashMap: операциите за вмъкване, търсене и изтриване се изпълняват средно за O(1) — константно време, благодарение на хеширането. В най-лошия случай (при колизии) сложността може да се влоши до O(n).

• TreeMap: базирана на червено-черно дърво, следователно операциите за вмъкване, търсене и изтриване се изпълняват за O(log n).

Така, времевата сложност на операциите с Map се определя от използваната реализация и обикновено е или O(1) (HashMap), или O(log n) (TreeMap).