On slide 22 in the tree slides it says that the complexity of trying every possible tree is O(2^n). I think this may be right as a lower bound, but I'm not sure it's the best thing to include. I added this comment in the powerpoint:
I think this the time complexity is actually worse, and might be more intuitively shown, as factorial in the number of data values. Is there a source that this O(2^n) is coming from?
On slide 22 in the tree slides it says that the complexity of trying every possible tree is O(2^n). I think this may be right as a lower bound, but I'm not sure it's the best thing to include. I added this comment in the powerpoint:
Anyone have a reference?