# Questions tagged [runtime-analysis]

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

981 questions
Filter by
Sorted by
Tagged with
1 vote
32 views

### Runtime complexity of permutation function

I am trying to find the asymptotic run time complexity of the following function which will return a list of all permutations of nums. ...
52 views

### Time Complexity for the given algorithm

Recently, I had to implement the following algorithm (similarly). Code in Kotlin: ...
37 views

16 views

### Runtime of the following procedure

I want to calculate the runtime of the following code as a function of n: ...
1 vote
30 views

### Is "Mutation" Cheaper than "Calculating Derivatives"?

When it comes to optimizing objective functions belonging to Statistical and Machine Learning Models, there seems to be a general rule: High dimensional objective functions with many parameters are &...
48 views

### confusion about Hopcroft-Karp time complexity analysis

From Wikipedia: "Each phase increases the length of the shortest augmenting path by at least one: the phase finds a maximal set of augmenting paths of the given length, so any remaining ...
103 views

### Analytic combinatorics and less-precise running times

Analytic combinatorics and concrete mathematics are the mathematics of asymptotic counting, and they draw from combinatorics, analysis, and probability. These techniques have been applied to the ...
1 vote
26 views

### Big theta and big 0 bounds for iteration method and Master Theorem

In Algorithms 1, I'm noticing that big-Theta running times are always used for recurrence relations when using the iteration method. Meanwhile, using the Master Theorem always seems to result in a big-...
47 views

### Solve the recurrence equation $T\left(n\right)\:=\:n\:+\:\sum _{i=1}^{n-1}\left(T\left(i\right)\right)$

I am trying to find the runtime of: $T\left(n\right)\:=\:n\:+\:\sum _{i=1}^{n-1}\left(T\left(i\right)\right)$ $T(1)= 1$ What is the way to solve this kind of problems?
22 views

### Define a directed edge in a DAG using partial ordering

I am trying to describe a novel type of DAG's construction algorithm. The directed edges of the graph corresponds to a partial ordering: i.e. any directed edge $e$ spanning from $f$ to $t$ also ...
1 vote
126 views

### Θ, O and Ω, and how they relate to each other as subsets

I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track. I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger ...
19 views

### NC with nearest neighbor gates

Consider a circuit belonging to the class $\text{NC}^i$, as defined here. From my understanding, the circuit consists of AND, OR ar NOT gates, each of bounded fan in --- without loss of generality, ...
48 views

### Time complexity of this for-loop

I know, the inner loop here is O(log n). But, I get confused by the multiplication in the outer loop part. ...
1 vote
115 views

### How many clock cycles are used to run my code?

Suppose that I want to know the number of the cycles of cpu clock that uses to run a specific code written with a specific programming language, like Python or others. Can I do it? I mean, do you have ...
43 views

1 vote
28 views

### Solve recurrence where the base case's time complexity is a function of the original input size

I'm trying to analyse the time complexity of the following algorithm for generating the power set: ...