Skip to main content
Share Your Experience: Take the 2024 Developer Survey

New answers tagged

0 votes

Emphasizing the Coefficients of the Leading Order and Using Big O Notation for the Remainder

Recall the definitions of various asymptotic notations. case 1: $f(n) = 2n^3 - 2n^2 + n + 1$ can be written as $f(n) = 2n^3 - g(n)$ where $g(n) = 2n^2 - n - 1$. Now $g(n) \in O(n^2)$ as well as $g(n) ...
codeR's user avatar
  • 1,042
1 vote

Optimal lookup complexity when requiring insertion complexity to be at most $\mathcal O(\log\log n)$?

After mulling this over for a long time, I've convinced myself that there is no optimal lookup complexity when insertion complexity is limited to $\mathcal O(\log\log n)$. I've written up my reasoning ...
Franklin Pezzuti Dyer's user avatar
3 votes

How to Determining the Big O Complexity of a Recursive Function?

The definition you've given for the sequence $f(n)$ is $$f(n) = \begin{cases} 0, &n = 1 \\ f(n-1) + f(\lfloor n/2 \rfloor), &n \ge 2 \end{cases} $$ Note that you've given $f(1)=0$, not $f(0)=...
Ashwin Ganesan's user avatar
4 votes
Accepted

How to Determining the Big O Complexity of a Recursive Function?

None of the answers are correct, the recursive equation $$T(n) = 1 + T(n-1) + T(\lfloor n /2 \rfloor), \quad T(0) = 1$$ gives solution $T(n) = {}$$\text{A346912}$$(n) = 2 \cdot $$\text{A000123}$$(n) - ...
orlp's user avatar
  • 13.6k

Top 50 recent answers are included