Я пытаюсь теоретически понять, сколько времени займет, когда входной размер, переданный для сортировки слиянием, удваивается. Я читал учебник, в котором говорилось, что:
"Поскольку время выполнения для сортировки слиянием (для большого N) равно O (N log_2 N), мы должны рассмотреть соотношение, r = N ^ {1.1} log_2 ( N ^ {1.1}) / (N log_2 (N)). Это упрощается до 1,1 N ^ {0,1}, что составляет около 3,5 "
. Я хотел спросить, как они вычислили, что это займет примерно в 3,5 раза больше времени? для сортировки слиянием, выполняемой, когда размер ввода удваивается. По сути, как они хотят об этой трансформации.