Ребята помогите разобраться, вроде просто, но не могу въехать. Вот допустим пусть имеется алгоритм, решающий задачу размера n за f(n) микросекунд. Каков максимальный размер задачи, которую он сможет решить за время t ? Найти его для функций и времён log n за одну секунду, за 1 минуту, за час. В книжке Кормена как то не понятно написано (по крайней мере для меня). Ну например для секунды получается что надо 1*10^6*log(1*10^6) . Но есть чуйка что это не правильно

Что подразумевается под функцией f? Какая-то конкретная функция? Тогда размером наверно будет f^-1(t). Если же имеется в виду o(n), т.е. время решения пропорционально размеру задачи, то и размер задачи, решаемой за время t должно быть пропорционально t. Не думаю, что есть смысл точно считать коэффициент пропорциональности, т.к. на время решения кроме алгоритмических вопросов влияет большое кол-во вопросов реализации.

Кроме того, говорить о максимальном размере задачи можно, по-моему, только если f(n) - нижняя оценка времени.