New answers tagged

0

The exact (time) cost of solving a problem depends on the computation model in use: Do you mean Turing machine steps, instructions of your PC, function calls in lambda calculus, ...? It turns out that you can simulate the usual computation models with each other in costs related by polynomials. E.g. $N$ CPU instructions can be simulated in $p(N)$ steps of a ...


0

$n+1 ≤ n^2$ for $n ≥ 2$, therefore $\log(n+1) ≤ \log (n^2) = 2 \log n$ for $n ≥ 2$, which by definition means $\log(n+1) = O(\log n)$. “Simplifying” is difficult. Let $f(n) = 2^{2^n}$, then $f(n+1) ≠ O(f(n))$. Same for $f(n) = n!$ Or more difficult to prove when $f(n) = \left|\sin(n)\right|$.


Top 50 recent answers are included