# Questions tagged [runtime-analysis]

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

1,046 questions
Filter by
Sorted by
Tagged with
13 views

### Why is the time complexity of bidirectional breadth first search still considered O(V + E)?

I understand that if the branching factor of the graph is b and distance of goal vertex from source is d, then the time complexity is O(b^d). I also understand why that would be O(b^d/2) using ...
• 121
1 vote
44 views

### What does "computer steps" mean in this runtime definition?

My algorithms textbook defines $T(n)$ as "the number of computer steps needed to compute fib1(n)" (where fib1(n) ...
• 111
22 views

### How is the prefix function (for KMP) time complexity O(N)?

I'm looking at the algorithm for the prefix function from here https://cp-algorithms.com/string/prefix-function.html : ...
• 324
37 views

### Is the Partition problem polynomial when all integers are large?

In the Partition problem, there are $n$ positive integers, and the problem is to decide whether they can be partitioned into two subsets with an equal sum. If all integers are "small" (at ...
• 6,070
1 vote
42 views

### Algorithms by Dasgupta-Papadimitriou-Vazirani Prologue confusion

We will see in Chapter 1 that the addition of two n-bit numbers takes time roughly proportional to n; this is not too hard to understand if you think back to the gradeschool procedure for addition, ...
• 111
57 views

### Precise definition of a brute force algorithm

What is the precise definition of a brute force algorithm? Is it one that simply has non-polynomial runtime?
• 154
49 views

### The Hydra Game runs forever

I saw this question here: The Hydra Game algorithm I am also running into troubles with the same problem. I also learned of the problem in this Numberphile video, and also tried to compute it myself. ...
• 1
26 views

1 vote
86 views

• 103
36 views

### If we find that, e.g., T(n)<=d*n*lg(n) for some d that depends on n, is T(n)=o(nlgn)?

In the substitution method, if we find that, for instance, T(n) < dnlg(n) but only for some d that depends on n, then can we say that T(n) = o(nlg(n)) (little-oh) in some cases? For example, in ...
40 views

### Function / Algorithm that take fixed time to compute

I was wondering if there are any mathematical functions or algorithms that take a known minimum amount of time to calculate. The closest thing I could find to this is Proof of Work algorithms used for ...
• 129
65 views

### Is time complexity $O(n^{n/log(n)})$ considered subexponential time?

If there is an algorithm with time complexity $O(n^{n/log(n)})$, is that already exponential time or still subexponential time? It shouldn't be considered quasi-polynomial since the exponent is also ...
37 views

### How can it be formally proved that $f \in O(⌊f ⌋)$

I'm trying to prove that $f \in \mathcal{O}(\lfloor f \rfloor)$ given that $\forall m \in \mathbb{N}, f(m) \geq 1$ Here's what I've thought of so far, we can set C = 10 and k = 1 and somehow prove ...
1 vote
555 views

• 101