Временная сложность и количество задействованных элементов

Question

Алгоритм A выполняет операцию временной сложности O (log n) в массиве, хранящем n элементов.

Алгоритм B выбирает log n элементов из массива и выполняет вычисление O (n) для каждого.

Поскольку d (n) = O (f (n)) и e (n) = O (g (n)), то d (n) * e (n) = O (f (n) * g ( n)), означает ли это, что оба алгоритма A и B имеют временную сложность O (n log n)?

Answer 1

Алгоритм A имеет временную сложность O (log n), а алгоритм B имеет временную сложность O (n * log n).Алгоритм B вычисляет что-то с O (n) на элементах log * nЯ предполагаю, что выбор эквивалентен сортировке.

Answer 2

Предполагая, что B не займет много времени, чтобы выбрать элементы, и вы имели в виду, что алгоритм A выполняет O (log n) для каждого элемента, да.