Вы правы, что время выполнения равно O (d (n + k)). Это может помочь явно определить связь между d и k. Если вы имеете дело с числами, которые идут от 0 до числа U, то число цифр base-k в каждом номере будет & Theta; (log k U) = & Theta; (log U / журнал к). Это означает, что время выполнения более корректно O (log U (n + k) / log k).
В вашем случае, k очень мало по сравнению с n, так что это время выполнения будет иметь значение для O (n log U / log k).
Ваше утверждение о том, что время выполнения будет & Theta (8 (10 + 20 000 000)) и & Theta (3 (1 000 + 20 000 000)), несколько странно. Помните, что & Theta; нотация говорит о долгосрочных темпах роста, а не об отдельных значениях, поэтому вставлять значения таким образом не имеет смысла. Тем не менее, ваш основной аргумент верен. Переход от базы 10 к базе 10000 в 3 раза увеличивает порядок основания, поэтому следует ожидать, что алгоритм будет примерно в три раза быстрее с большей базой.
Тем не менее, есть много других факторов, которые могут испортить это время на практике. Локальность ссылок играет огромную роль во время выполнения алгоритмов, которые выполняют множество манипуляций с массивами, и с увеличением количества сегментов вы получаете прогрессивно худшую локальность. На самом деле это может привести к тому, что сортировка с более крупным основанием будет медленнее, чем сортировка с меньшим основанием, поскольку, хотя количество раундов меньше, каждый раунд занимает больше времени из-за эффектов кэширования. Не попробовав этого, я бы держал пари, что есть хороший шанс, что это произойдет на практике.