Trie data structure space usage in Java

Question

I just want to double check the total space that a Trie data structure could have in the worst case. I thought it would be O(N*K) where N is total number of nodes and K is the size of the alphabet (points to other tries), but people keep telling me it's O(K^L) where where K is the size of the alphabet and L is the average word length, but do those null pointers use up memory space in Java ? for example, if one of the node only has lets say 3 branches/points out of total size K. Does it use K space ? or just 3 ? The following is Trie implementation in Java

class Trie {
     private Trie [] tries;

     public Trie () {
          // A size 256 array of Trie, and they are all null
          this.tries = new Trie[256]; // K = 256;
     }
}

Answer 1

If the memory footprint of a single node is K references, and the trie has N nodes, then obviously its space complexity is O(N*K). This accounts for the fact that null pointers do occupy their space. Actually whether an array entry is null or any other value doesn't change anything in terms of memory consumption.

O(K^L) is a completely different measure because it uses different parameters. Basically K^L is the estimate on the number of nodes in a densely populated trie, whereas in O(N*K) the number of nodes is explicitly given.