# Questions tagged [runtime-analysis]

Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.

862 questions
Filter by
Sorted by
Tagged with
2k views

### For what kind of data are hash table operations O(1)?

From the answers to (When) is hash table lookup O(1)?, I gather that hash tables have $O(1)$ worst-case behavior, at least amortized, when the data satisfies certain statistical conditions, and there ...
2k views

### Complexity of dynamic programming algorithm for Knapsack

Dynamic programming algorithm for Knapsack is stated to have complexity $\mathcal O (nW)$. However, I've also seen the complexity stated as $\mathcal O (n^2V)$, where $V=\max v_i$. (Here $n$ is the ...
101 views

### Time complexity of $\sim c \cdot n^3$ with a computer which is 10 times faster

I am trying to solve the following question There's an algorithm with time complexity $\sim c \cdot n^3$. Suppose there's another computer which is 10 times faster. How much bigger can our $n$ ...
1k views

### Ford-Fulkerson Running Time

This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them! In the analysis of Ford-...
64 views

### Complexity terminology

What is the terminology used for speaking about complexity, when we don't study it asympotically (but exactly) ? Thank you
286 views

269 views

### Big-O Time Complexity of nested for loops [duplicate]

My gut tells me the time-complexity of the following code is simply O(n^2). However, I'm not convinced, thinking it could possibly be O(n^3): ...
739 views

### Runtime of a recursive algorithm

I have a simple recursive solution as below: ...
8k views

### Finding the time complexity of fibonacci sequence [closed]

I tried it as follows and would like to know if it is correct.
802 views

### Count comparisons in insertion sort that uses binary search to find correct postion

Assume a list $L$ is to be sorted using the following variation of insertion sort: For $2 \le i \le n$, to insert key $L[i]$ do a binary search on the list $L[1..i-1]$ to find the correct position. ...
I understand that segment trees can be used to find the sum of sub array of $A$. And that this can done in $\mathcal{O}(\log n)$ time according to the tutorial here. However I'm not able to prove ...