# Questions tagged [runtime-analysis]

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

111 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k views

### Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
228 views

81 views

### Examples of context-free grammars with worst-case complexity

What are some examples of context-free grammars that necessarily trigger cubic worst-case complexity for GLR parsers? I have seen a mention of the example S $\rightarrow$ SSS | SS | "a" but I would ...
376 views

### One algorithm for turnpike reconstruction problem?

In << Data Structure and Algorithm Analysis >>, turnpike reconstruction problem is given for demo of backtracking. Suppose we are given n points, p1 , p2 , . . . , pn , located on the X -axis. ...
176 views

### How does one heuristically determine if an algorithm has an exponential time complexity?

How does one easily determine if an algorithm has an exponential time complexity? The Word Break naive solution is known to have a time complexity of O(2n) but most people think its O(n!) because of ...
255 views

427 views

### Bridge Crossing Problem Proof?

I'm trying to find an optimal solution that will work for the bridge crossing problem. In case you don't know it you can check out the Ted Ed video on it. They show how you can do it with 5 people but ...
283 views

### How to determine big O of a variable loop

I want to classify the runtime of this function in big O notation. This function is multiplying two whole numbers and checks the in binary digits of the multiplicand. And adding the multiplier to the ...