如何计算一个算法在运行时间t内输入n的最大大小O(2log(n))？

Question

对于函数 f(n) 和时间 t 在下表中，确定最大的尺寸。n 的 O(log(n)^2) 及时解决 t，假设求解该问题的算法需要 f(n) 微秒]

下面是一个比较详细的问题的图片和要填的表格。

Answer 1

O的符号是渐进式的，所以你不能精确计算算法的运行时间。如果你假设O=OMEGA，并假设对小n也有很好的近似性，并且有差不多一个值的测量，就可以近似计算时间。