Его временная и пространственные сложности равны O(b^d), а не O(b^(d+1)).Это написано даже в книге, на которую ссылаются.