在二叉排序树中插入一个新节点的平均时间复杂度为O(log n)，这是因为在平衡的二叉排序树中，每次插入操作都大致将搜索空间减半。选项A表示常数时间复杂度，不适用于插入操作；选项C表示线性时间复杂度，适用于最坏情况；选项D表示线性对数时间复杂度，不是插入操作的时间复杂度。