Ответ
В среднем случае добавление ключа в map в Go имеет сложность O(1) (амортизированная константная сложность), так как используется хеш-таблица.
В худшем случае (из-за коллизий и рехеширования) сложность может достигать O(n), но на практике это крайне редкая ситуация.
Пример:
m := make(map[string]int)
m["key"] = 42 // O(1) в среднем