Share Your Experience: Take the 2024 Developer Survey

# Tag Info

Accepted

• 1,248
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)...
• 651

### 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 ...
• 30.4k
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$ ...
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 ...
• 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 ...
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 ...

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