Какова временная и пространственная сложность кодирования Хаффмана?

Я реализовал алгоритм кодирования Хаффмана, используя (две) хэш-карты для хранения частоты и кода каждого уникального символа (хранящегося как ключи в хэш-картах) (хранящегося как значение в хэш-картах). Я не уверен, как я могу определить сложность времени и пространства, может ли кто-нибудь помочь мне узнать и объяснить, что это такое?

У меня есть некоторые мысли: каждый уникальный символ хранится один раз в каждой хэш-карте, так что сложность пространства O (2 * n) = O (n)?

Я читал, что временная сложность составляет O(nlogn) (для некоторых решений), но не понимаю, почему это так.

Сначала я строю карту частот из строки:

/**
 * builds a list of the occurring characters in a text and
 * counts the frequency of these characters
 */
public void buildFrequencyMap(String string) {
    frequencyMap = new HashMap<Character, Integer>(); //key, value
    char[] stringArray = string.toCharArray();

    for(char c : stringArray) {
        if(frequencyMap.containsKey(c)) { //if the character has not been stored yet, store it
            frequencyMap.put(c, frequencyMap.get(c) + 1);
        } else {
            frequencyMap.put(c, 1);
        }
    }
}

Затем я строю дерево:

/**
 * builds the huffman tree
 */
public Node buildTree() {
    PriorityQueue<Node> queue = new PriorityQueue<Node>();

    //fill the queue with nodes constructed from a character and its frequency
    for(char i = 0; i < 256; i++ ) { //256 - size of ASCII alphabet
        if(frequencyMap.containsKey(i) && frequencyMap.get(i) > 0) {
            queue.add(new Node(i, frequencyMap.get(i), null, null)); //create new leaf
        }
    }

    //if the indata only consists of 1 single character
    if(queue.size() == 1) {
        queue.add(new Node('\0', 1, null, null));
    }
    //otherwise
    //continuously merge nodes (two with the lowest frequency) to build the tree until only one node remains --> becomes the root
    while(queue.size() > 1) {
        Node left = queue.poll(); //first extracted child becomes the left child
        Node right = queue.poll(); //second extracted child becomes the right child
        Node parent = new Node('\0', (left.frequency + right.frequency), left, right);
        queue.add(parent);
    }
    return root = queue.poll(); //the remaining node in the queue becomes the root
}

Наконец, кодовая карта построена:

/**
 * builds the codemap
 */
public void buildCodeMap() {
    codeMap = new HashMap<Character, String>(); //key, value
    buildCode(root, "", codeMap);
}

public void buildCode(Node node, String code, HashMap<Character, String> codeMap) {
    if(!node.isLeaf()) { //if the current node is NOT a leaf
        buildCode(node.leftChild, code + '0', codeMap); //each time we go down at the LEFT side of the tree, encode a 0
        buildCode(node.rightChild, code + '1', codeMap); //each time we go down at the RIGHT side of the tree, encode a 1
    } else { //otherwise
        codeMap.put(node.character, code);
    }
}