Questions tagged [runtime-analysis]
Questions about methods for estimating the increase in runtime of an algorithm as the input size increases.
1,023
questions
1
vote
0
answers
44
views
Computational complexity of an algorithm involving permutations
I'm interested in getting a precise estimate of the computational complexity of an algorithm I wrote involving permutations. Permutations are represented in my code as arrays of the integers $1$ ...
- 113
0
votes
0
answers
35
views
Running time of variant of Dijkstra's algorithm
Consider the problem of finding the shortest-path distances from an origin vertex to all other vertices in a digraph. Normally in Dijkstra's algorithm, we visit the vertex whose shortest distance from ...
- 287
0
votes
2
answers
61
views
Minimum number of comparisons to find $2$nd smallest element
Show that the second smallest of $n$ elements can be found with $n+\lceil\lg n\rceil-2$
comparisons in the worst case. (Hint: Also find the smallest element.) [1]
I tried but I have no idea how to, e....
- 129
0
votes
1
answer
53
views
Optimizing findMissingNumber algorithm to O(N)
This problem is from Cracking the Code Interview:
An array A contains all the integers from Oto n, except for one number
which is missing. In this problem, we cannot access an entire integer
in A ...
- 1
0
votes
1
answer
37
views
Is it an open problem if CDCL algorithms violate SETH?
Strong Exponential Time Hypothesis states that general SAT, where clauses are not limited in length, can't be solved in time $o(2^n)$. It's proven that DPLL algorithm requires $\Omega(2^n)$ time in ...
- 1,393
-1
votes
2
answers
63
views
Finding asymptotically tight upper bound of a recursion relation
Find an asymptotic tight upper bound for the following recursion relation: $$T(n)=5T(\frac{n}{5})+\log^2(n)$$
I tried to solve it by applying iteration:
$$T(n)=5T(\frac{n}{5})+\log^2(n)=5(5T(\frac{n}{...
- 99
0
votes
1
answer
18
views
How branching factor affects complexity of Monte Carlo Tree Search?
I was reading: https://stackoverflow.com/questions/34724201/whats-the-time-complexity-of-monte-carlo-tree-search
Where it says:
The runtime of the algorithm can be simply be computed as O(mkI/C)
...
- 1
0
votes
0
answers
6
views
Asymptotics Accounting for Invocation Frequency in the Context of the broader system
I did some thinking and analysis this evening and I'm wondering if what I'm pointing out here is interesting:
https://medium.com/@nwcodex/invocation-asymptotics-runtime-cost-based-on-the-anticipated-...
0
votes
0
answers
39
views
Parallel Algorithm Analysis: Loops
I have come across what seems to be a collapsed loop.
parallel-for i, j = 1...n
What would be the work and span/depth/critical path length be of loops like this? ...
- 11
0
votes
0
answers
26
views
I/O Complexity Analysis with Memory Hierarchies
How to go about analysing the I/O complexity when there are multiple levels of memory involved? Looking up I/O complexity analyses returns papers such as this one, which generally assume for ...
2
votes
0
answers
52
views
Algorithm to compute sum of quotient polynomials
Let $f(X)$ be a polynomial in $\mathbb{F}_p[X]$ for some prime $p$ (of size 256 bits) that is not necessarily FFT-friendly. Let $a_1,\cdots,a_n$, $b_1,\cdots, b_n$ be $\mathbb{F}_p$ elements.
What is ...
- 93
18
votes
4
answers
2k
views
Measuring time complexity in the length of the input v/s in the magnitude of the input
I know that formally the time compliexity of an algorithm is measured in the length of the input, which in binary would be the number of bits required to encode the input.
The problem that I have with ...
- 183
1
vote
0
answers
34
views
What is the worst case time complexity of unranking n choose k combinations (combinatorial number system, combinadics)
The combinatorial number system shows that there is a bijection between the natural numbers less than $n \choose k$ and $n\choose k$ combinations. There is a greedy algorithm for unranking ...
- 111
0
votes
3
answers
60
views
How do you stop an algorithm at a specific run time?
so I'm trying to write an algorithm in C to play the game of Reversi. I've already written in basic minimax algorithm yet I am not very satisfied with it. I want to implement alpha-beta pruning to my ...
- 101
0
votes
0
answers
72
views
Recurrence relation for TSP using recursion
This is a Python algorithm using recursion to solve Travelling Salesman Problem, consider $G$ a complete graph:
...
- 101
0
votes
1
answer
39
views
How do you calculate the amount of iterations the loop "for (i = 1; i < n^3; i += n)"
How do you calculate the amount of iterations the following loop will have in terms of n?:
for (i = 1; i < n^3; i += n) {
}
I've gotten as far as: $$i=(x-1)...
0
votes
2
answers
51
views
Can a program that terminates have a running time of infinity? (Or not have an upper bound)
Can we have an algorithm that takes some input and does something random to it (in such a way that the algorithm does terminate) which does not have a worst-case running time upper-bound?
A (non-)...
- 359
0
votes
1
answer
41
views
A Problem with Solving a Recurrence relation
I Hope someone Can help me with that:
$T(1)=2$
$T(n)=\left(T(\frac{n}{2})\right)^2\cdot2^n $
what is the runtime complexity of the algorithm (base 2)
Thanks a Lot!
- 1
-2
votes
1
answer
32
views
Solving a recurrence relation formula with squared
I hope someone can help me with that:
$$T(n)=T(2^{\sqrt{\log n}})+1$$
I will be asked to answer what is the runtime complexity of the algorithm.
I tried to set m=2^ and still failed.
- 1
0
votes
2
answers
38
views
Dropping terms in proving the runtime for a recurrence?
I am trying to learn how to prove the runtime of a recurrence relation, particularly through induction. I was looking at this lecture PDF, and on the first page, the author writes this:
Recurrence: $...
- 103
-1
votes
2
answers
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 ...
0
votes
2
answers
32
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
0
votes
1
answer
56
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 ...
user154939
0
votes
1
answer
33
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
2
answers
359
views
Can dot producting the result of vector-matrix multiplication speed up the runtime?
Suppose we have a matrix $A$ of dimension $n \times n$ and two vectors $\vec{u}$ and $\vec{v}$ of dimension $n$.
Then we have $A\vec{v} = \vec{x}$ with time complexity $O(n^2)$ and space complexity $O(...
- 177
0
votes
0
answers
51
views
I would not be able to get my simulation in my life time
I am running a simulation on my computer. I tried to multiply two polynomials $g(x), h(x)\in GF(2)[x]$, with $degree(g(x))= 8165$, and $degree(h(x))=25$. This multiplication took almost $20$ minutes ...
- 101
0
votes
1
answer
117
views
0
votes
0
answers
68
views
What is the expected time complexity of this algorithm?
In the following algorithm $A[1..n]$ denotes an array $A$ of size $n$, of $n$ distinct integers. Func1() and Func2() are functions that run in $\mathcal O(\log n)$ and $\mathcal O(n)$ time, ...
- 257
3
votes
0
answers
37
views
TSP algorithm with a good run-time based on properties of the graph (not just based on number of nodes/edges)?
In the worst case, the Traveling Salesperson Problem (TSP) is mostly accepted to take exponential runtime in terms of $|V|$ and $|E|$ (the number of vertices and edges respectively). But for many real-...
- 512
2
votes
1
answer
66
views
Complexity of right-to-left Knuth-Morris-Pratt algorithm
Suppose we modify the Knuth-Morris-Pratt string-matching algorithm to scan the pattern right-to-left a la Boyer-Moore, and consequently apply the shift rule on the right side of the cursor instead of ...
- 183
0
votes
1
answer
36
views
What are the actual costs $c_i$ in the potential method?
In "Introduction to Algorithms" by Cormen et al. the Potential Method is explained. For example, we have the following representation for the amortized costs of the i-th operation with ...
- 103
0
votes
0
answers
82
views
Analysis of randomized algorithms
The expected running time, $T(n)$, of quicksort when the pivot is chosen uniformly at random satisfies $$ T(n) \leq \mathcal O(n) +\frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n - i)),$$
which leads to the ...
- 257
1
vote
1
answer
97
views
Show that $TIME(\sqrt{n})$ = $TIME(1)$
Also known as CMU 15-455, Spring 2017, Homework 2.4.
Before I ask the main questions, let me first give a sketch of my idea. First, recall the definition of big-$O$ and time complexity class $TIME(t(n)...
- 11
2
votes
1
answer
53
views
Sieve of Eratosthenes for factorization: bitwise complexity?
As is well-known (and easy to prove), carrying out a sieve of Eratosthenes on the first $N$ integers takes a number of word operations in the order of $N \sum_{p\leq \sqrt{N}} 1/p \sim N \log \log N$, ...
- 241
1
vote
2
answers
161
views
How can we prove that "extract almost minimum" operation in a priority queue cannot be done in o(log n)?
Suppose we want to create a priority queue with 2 operations: insert and extract almost min. Extract almost min operation selects either the first minimum or a second minimum item from the structure ...
- 57
0
votes
0
answers
40
views
Runtime Analysis of Uniform Sampling via exact degree computation
Let $\mathcal{A} \subseteq \mathcal{B}$ given as a collection of arrays. The degree of an element $a \in \cup \mathcal{A}$, is the number of sets of $\mathcal{A}$ that it contains - that is, $d_{\...
- 123
0
votes
2
answers
54
views
Finding the runtime out of a recursion formula when using divide-and-conquer
In divide-and-conquer, one uses the following formula to find the runtime:
$$T(n) = aT(n/b) + f(n).$$
I am confused with the meaning of the constants $a$ and $b$, as well as by the question of how to ...
- 113
1
vote
2
answers
83
views
Average runtime random search without replacement
Consider an algorithm that is tasked with searching the array A. Let n be the size of the array, let i be a random number between 1 and n. Finally, k is the target object we are searching for. If A[i] ...
0
votes
1
answer
50
views
In the Master Theorem, if one term is smaller than another, can we drop it from the equation and use big O instead of theta?
Considering the runtime analysis (with the master theorem) of the function below
$T(n) = 12T(\frac{n}{4}) + 2\sqrt{n} + \log^4(n)$.
As I could not figure out a way to get the equation in the form $T(...
- 101
11
votes
3
answers
3k
views
Is Big-Theta a more accurate description of worst case run time than Big-O?
Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?"
To me, the only difference is that when we say $O(...
-1
votes
1
answer
85
views
Help me solve recursion equation by using recursion tree method
Hello I am trying to solve this recurrence equation using the recursion tree method:
T (n) = T (n −1) + n^2 In particular, what is big-O of T (n)?
Here is what I have done so far:
I am not sure if I ...
- 3
-3
votes
2
answers
50
views
Iterative solution of recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$
Please help me to find the Time Complexity of the recurrence relation $T(n)=4T(\frac{n}{2})+\frac{n^3}{log_2n}$ using iterative method.
- 1
1
vote
0
answers
39
views
Probability that an Algorithm Deviates from Its Behaviour after Multiple Rewindings
I do have a seemingly fundamental question that I somehow struggle to intuitively make sense of.
Setting:
Let us consider a randomized algorithm $R$ that has $t$ steps. In each step, it is fed with ...
- 11
1
vote
1
answer
74
views
Time complexity for finding the number of triangles in a graph
In our class we considered the problem written in the title. The below given time complexities where simply given, but not derived or explained. Therefore I tried myself to derive them, while I using ...
- 185
1
vote
1
answer
91
views
Turing machine read time
Suppose I have a Turing machine that takes as input any string of length $n$, where $n$ is odd, and the Turing machine returns the middle character of the string.
What time complexity class is this in?...
- 271
0
votes
2
answers
38
views
Loops running time as function of n
Suppose I have the following code and I'd like to compute running time as function of $\ n$:
...
- 157
1
vote
4
answers
152
views
What happens to the running time if we reduce the size of input?
Let there is an algorithm whose running time is $O(n^2)$. Suppose we apply a preprocessing step on the algorithm in $O(n)$ so that it reduces the input size to $O(\sqrt{n})$ but doesn't effect the ...
- 1,509
1
vote
0
answers
40
views
k-Circle Cover - How to show the faster algorithm isn't slower
I am having two algorithms, of which the second is a refinement of the first. However, I am having trouble to show that the seemingly better algorithm runs at least as fast as the first algorithm.
The ...
- 659
2
votes
1
answer
109
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.
...
- 21
0
votes
1
answer
163
views
Time Complexity for the given algorithm
Recently, I had to implement the following algorithm (similarly). Code in Kotlin:
...
- 101