Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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
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
3 votes
Accepted

Why do we use summations when computing time complexity?

I think you might be slightly confused about what the notation $$\sum_{i=1}^n$$ means. In particular, it doesn't actually mean anything. There needs to be something "inside" (to the right of)...
NaturalLogZ's user avatar
2 votes

Understanding Time Complexity Calculation for Factorial and Exponential Algorithms

All possible paths in a graph: If all nodes are connected, you have 100 nodes, and the start node is given, you can move to one of 99 nodes. If you don't want to visit the same node twice, you can ...
gnasher729's user avatar
  • 30.4k
2 votes
Accepted

Solving recurrence relation $T(n) = \max\{T(k)+T(n−k)+O(\min\{k, n-k\})\}$

It gives $T(n) = O(n \log n)$. Let's prove by induction that $T(n) \le Cn \log n$, for some big enough $C \in \mathbb{R}$: The induction hypothesis is that $T(n) \le C n \log n$. Now take $T(1) = 0$ ...
izanbf1803's user avatar
1 vote

Algorithms by Dasgupta-Papadimitriou-Vazirani Prologue confusion

Look at the definition of fib1. It computes one addition in this call, namely fib1(n-1) + fib1(n-2) and then some additions in ...
Pål GD's user avatar
  • 16.5k
1 vote

Understanding Time Complexity Calculation for Factorial and Exponential Algorithms

I'm particularly confused when trying to calculate the time complexity of algorithms that explore all possible paths in a graph. Consider a graph $G$ of $n$ vertices. Assuming all pairs of vertices ...
Ziad Ismaili Alaoui's user avatar
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

Only top scored, non community-wiki answers of a minimum length are eligible