Share Your Experience: Take the 2024 Developer Survey

# Tag Info

## New answers tagged asymptotics

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) ... • 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 ... 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)=...
• 1,258
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) - ...