Questions tagged [analysis-of-algorithms]
Questions concerning estimations of the amount of time and space used by an algorithm. Approximate recurrence relations are considered. For exact recurrences use [tag:recurrence-relations] or [tag:functional-equations].
123
questions
0
votes
0
answers
28
views
Search Algorithm: Combination of two numbers (Proof)
In several applications or examples in Computer Science (Algorithms & Data Structures), one needs to find two numbers $a_S$, $b_S$ out of two different ordered sequences $A$ and $B$ which summed ...
- 238
0
votes
0
answers
12
views
Validity of alternative algoritm for converting to RREF (row reduced echelon form)
I was writing a code in Python to convert a matrix (general) to row reduced echelon form. I've not really studied many different algorithms for doing so and my knowledge is based on the courses in my ...
- 176
0
votes
0
answers
29
views
Pollard's rho factorization turns out slower than trial division?
Learning basic number theory, I wrote a simple program to factorise integers by trial division. The next task was to learn and implement Pollard rho algorithm (hopefully, order(s) of magnitude faster ...
0
votes
0
answers
55
views
Number of digits in a computation involving integers with different number of digits
Compute $\max(A+B, C+D) + E$ where $A,C$ have $n$ digits, $B,D$ have $3n$ digits, $E$ has $2n$ digits
What will be the primitive operations?
What will be the output digit?
Hi for the above question I ...
0
votes
1
answer
61
views
What is a mathematical defintion for a curried procedure?
What it means to curry a function in computer programming?
In the field of computer programming, the word curry is used to describe functions $f$ such that for any positive whole number $n$ the ...
- 917
-2
votes
0
answers
9
views
The amortized complexity of visiting $m$ keys in order in B-tree with $N$ items
I read a paper that said the amortized complexity of visiting $m$ keys in ascending order in a $b$ tree with $N$ keys is $O(1 + \log(N/m))$. I am wondering why it is not $O(1 + (\log N)/m)$ because ...
0
votes
0
answers
21
views
Prove that the growth rate of one function is bigger than the other
Part of the exercise from "Algorithms Illuminated" book.
Arrange the following functions in order of increasing
growth rate, with g(n) following f (n) in your list if and only if
f (n) = O(g(...
- 21
1
vote
1
answer
33
views
Where did I go wrong with this algorithm analysis? I was asked to calculate k.
The question says that $x$ and $y$ are in the form of $2^P$. So I assumed that meant:
$x =$ $2^{p_1}$;
$y =$ $2^{p_2}$;
...
- 25
2
votes
0
answers
209
views
Two-sum problem with $n$ iterations
Preamble:
The famous two-sum problem asks for an algorithm to determine if a given integer $s$ is the sum of two integers in a given ordered list $L$. If $n$ is the size of $L$, this can be solved in $...
- 12k
0
votes
0
answers
52
views
How to prove the Amortized cost of this branching function?
bool function0(int x){
if (x == 1) return true;
if (x == 0 || (x % 2 != 0)) return false;
if (x > 1) return function0(x/2);
}
So my understanding of ...
- 23
0
votes
1
answer
18
views
Size of the Partitions of Quicksort
We are partitioning a sequence of $n$ elements, obtaining two partitions with $n-1$ total elements (an element is consumed as the pivot).
My textbook says in a best-case split, the partitions have ...
- 19
0
votes
0
answers
47
views
Maximum matching = Minimum odd vertex cover
Definition:
A set $C⊆V$ and a collection of subsets $𝐵_1,…,𝐵_𝑘⊆V$ is an odd vertex cover if for every edge 𝑒 either $𝑒∩𝐶≠∅$ or $𝑒 ⊆ B_i$ for some 𝑖.
The cost of the odd vertex cover is ...
- 7
-1
votes
1
answer
74
views
Minimize $\sum_{e \in E} w(e)x_e$ [closed]
Is the following formulation of the un-directed minimum spanning tree (MST) aproblem? Minimize $\sum_{e \in E} w(e)x_e$. Subject to:
$\sum_{e \in \delta(S)} x_e \geq 1$ for all $S \subset V, S \neq \...
- 7
0
votes
0
answers
32
views
Finding MDST in subgraph is enough for MDST problem in the original graph
Let $G = (V, E, w)$ be strongly connected graph. Show that there exists a subgraph $G′ = (V, E′, w)$ of $G$ with $|E′| \le 2(n − 2)$ such for every $r\in V$ , an MDST of $G′$ rooted at $r$ is also an ...
- 7
0
votes
1
answer
72
views
0
votes
0
answers
23
views
Upper Bound to PoS of a congestion game with max λ players using a resource
Good morning everyone, I've been reasoning on this problem for severeal days, but I couldn't end up with a solution.
Consider a congestion game for which we have the following guarantee:
The cost ...
- 1
0
votes
0
answers
52
views
K-vertices with least distance to subset of other vertices in a graph
Given an undirected graph $G=(V,E)$ where $V=\{v_1,v_2,...,v_n\}$ denotes the vertices and $E=\{e_1,e_2,...,e_m\}$ denotes edges. Moreover, there exists a nonnegative weight associated with each edge.
...
- 21
0
votes
0
answers
11
views
Show that for every hash function h: U → {0, 1, . . . , m − 1} there exists a sequence of m insertions into an empty hash table T of length m..
I'm currently trying to solve this task:
Let $|U| = m^2$ and suppose that collision is solved by chaining. Show that for every
hash function $h: U → \{0, 1, . . . , m − 1\}$ there exists a sequence of ...
- 1
0
votes
0
answers
33
views
Finding time complexity of the minimal element in hash table?
I want to understand and solve the next task: If we draw elements from a universal set U and insert n (different) elements into ...
- 1
1
vote
1
answer
62
views
Is the minimum spanning tree always the optimal solution of spanning tree polytope?
I was studying the proof of $1.5$-Approximate Path TSP problem and found a tiny wrinkle that I just can't get over it.
In the proof it says that the minimum spanning tree found by standard MST ...
0
votes
0
answers
9
views
Series sustainability on certain level in stock market
I have calculated strength of each candle for day. This value has sharp spike on start of the day when there is huge amount of volume.
Over the whole day value keeps on decreasing. But sometimes there ...
- 101
1
vote
1
answer
62
views
Does CR for positive definite matrices have the same convergence theorem as CG?
The conjugate residual (CR) algorithm (specifically for symmetric positive definite matrices) differs from the conjugate gradient (CG) algorithm in a very slight way. I am using this as a reference. ...
- 580
0
votes
1
answer
48
views
A version of an algorithm for an "uniform" subset sum problem?
Let $l_1,\cdots,l_n \sim U(0,1)$ be i.i.d uniform variables. Given $L>0$ a natural number, let us define the "uniform" subset sum problem as:
Find $I \subset \{1,\cdots,n\}=:[n]$ such ...
- 555
3
votes
0
answers
84
views
Estimation the computation complexity of algorithm with more that one choice
The problem:
We have a weighted graph $G=(V, E, W)$ with $|V| = n$, $|E| = n-1$ and $W$ is set of edge's weight. The graph $G$ includes one ring on $n_1 \geq 3$ nodes and $n_2$ isolated nodes, $n_1+ ...
- 1,221
0
votes
1
answer
31
views
How to determine computational efficiency of different formulas?
I am not sure whether or not the speed at which computers can compute a formula heavily depends on the calculating program or not. My question will assume there is a significant difference though, and ...
- 956
1
vote
1
answer
21
views
From combinatorial embedding to DCEL in linear time
The problem:
We have a planar graph $G=(V,E)$ with $|V| = n$, given as input in the form of a combinatorial embedding.
We want to build a DCEL (doubly connected edge list) in $\mathcal{O}(n)$ time - ...
- 4,053
0
votes
0
answers
6
views
A question about integrality gap, approximation ratio
I am reading the paper on RPR2 rounding on approximation ratio of MaxCut problem. See this link. There is one sentence which is important to me but I don't understand its logic. I quote it here:
If ...
- 479
1
vote
0
answers
22
views
Asymptotic notation in equations
I've been working my way through Introduction to Algorithms, Fourth Edition and am having a hard time with one of the exercises in chapter 3, which is mostly about standard notation.
The exercise is ...
- 111
1
vote
1
answer
90
views
Maximum constant $c$ for which $F_n = \Omega(2^{cn})$, where $F_n$ is the Fibonacci sequence
What is the maximum real constant $c$ for which $F_n = \Omega(2^{cn})$, where $F_n$ is the Fibonacci sequence?
I figured out that I have to calculate the maximum $c$ for which the limit $\lim_{n \to \...
- 515
0
votes
1
answer
53
views
Why is $M\left(\frac{n}{2}\right) + M\left(\frac{n}{4}\right) + \ldots + M\big(1\big) = O\big(M(n)\big)\,$?
We are given a sequence $M(n)$ and we know that $M(n) = O\left(n^2\right)$. Why does it follow that $M\left(\frac{n}{2}\right) + M\left(\frac{n}{4}\right) + \ldots + M\big(1\big) = O\big(M(n)\big)\,$?
...
- 515
0
votes
0
answers
40
views
Is there a closed form for following binomial series?
Currently I practice analyzing various algorithms for time complexity. For minimal vertex cover I came across an algorithm based on binary search. I figured out time complexity is the following series ...
- 11
1
vote
1
answer
22
views
How is the lower bound calculated for permutation of numbers in the backtracking algorithm?
I was reading this for calculating permutation of numbers https://keaoxu.files.wordpress.com/2018/08/permutation_output_algo_analysis.pdf where a backtracking solution time complexity is presented.
...
- 131
2
votes
1
answer
82
views
Find upper bound for T(n) in terms of n and prove with Master Theorem
Sorry about the formatting. Had nothing but my cellphone!
Problem: Suppose this is an algorithm that runs in T(n) time, where T(n) is the following recurrence relation:
T(n) =
$2T($$ \frac n3$$) + Θ(...
- 23
0
votes
0
answers
15
views
Maximum number of jobs with $k$ servers
Consider an array of jobs, each having a specific start time and end time and we have $k$ servers. What is the maximum number of jobs that can be scheduled such that no two jobs in a server is ...
- 199
0
votes
1
answer
55
views
What is the time complexity of this permutation algorithm?
The algorithm is as follows:
...
0
votes
0
answers
29
views
Shortest paths: Does $d(s, t) = d(s, v) + d(v, t ) $ always hold if $v \in p $ where p is the shortest path between $s, t$?
Now I know that there is a distinction between single source shortest path algorithms and all-pair shortest path algorithm . My question is the following:
If we solve the single source (let's say s ) ...
- 729
0
votes
1
answer
132
views
Algorithm finding maximum of array O(log n)?
Does there exist an algorithm that can output the maximum value of an array in O(log n) time? An O(n) algorithm is quite obvious:
1.
But I would want to know if an O(log n) algorithm exists. The same ...
- 289
0
votes
1
answer
22
views
What's the relation between these two definition of Ackermann function?
The definition 1 is from Introduction to Algorithm and the second is from wikipedia.
- 69
1
vote
0
answers
34
views
Is the sequence produced by this algorithm decaying as $\frac{c}{\sqrt{t-t_0}}$?
This is a messy problem, but maybe could be interesting for someone who has the inclination. It came out analyzing a subroutine of an optimization algorithm. I'll post it here as a question, even ...
- 5,343
0
votes
0
answers
25
views
Arnoldi iteration on constant number of iterations and variable matrix size.
I'm trying to get some insight into the convergence of the Arnoldi method when the number of iterations is constant, but the matrix size is not. I'm assuming that most of the eigenvalues are located ...
- 1
1
vote
0
answers
26
views
How to call the property that says that a heuristic is able to find the optimal solution?
Given a heuristic approach to solving an optimization problem, does there exist a name for the property that says that this heuristic is able (but might not be guaranteed) to find the optimal solution?...
- 111
0
votes
1
answer
26
views
Resources for a simple introduction to computational complexity
I study mathematics and want to do my end-of-degree project on heuristic methods for optimization (more concretely, genetic algorithms) and wanted to include a section on computational complexity. ...
- 349
4
votes
0
answers
33
views
Amortized analysis of append with non-constant growth factor
I'm trying to show that $n$ append operations on a dynamic array run in $O(n)$ time for the growing strategy of allocating an array of capacity $N+\lceil\frac{N}{4}\rceil$ when the old array of ...
- 203
0
votes
0
answers
30
views
Scalar "Triangle Inequality" for Logarithms
I'm trying to create an algorithm that merges two sorted arrays of integers of lengths $m$ and $n$ with an overall time complexity of $T(n) = O\left(\log_2(n + m)\right)$, where $T(n)$ represents the ...
- 75
0
votes
1
answer
31
views
NP problem in $\mathit{TIME}(f(n))$
This is a task in Algorithm theory course I cannot wrap my head around.
Assume a problem $ R \in \mathit{NP} $ can be solved with $M(x,y)$ and it solves in $O(n^3)$ with additional information $y$ ...
- 43
0
votes
1
answer
47
views
Justifying that ISOLATED problem belongs to SPACE(log n)
There is this problem in my Algorithm theory course for getting ready for exam and I just can't wrap my head around this
The problem ISOLATED: given a graph $G$ verify that there is a vertex $v$ for ...
- 25
2
votes
2
answers
110
views
Computational cost/complexity of algorithms based on the number of mathematical operations
A problem is made up of $n$ similar parts. There is an algorithm $A_1$ to solve one of those parts using, for example, 10 divisions and 5 additions. Therefore, I apply the algorithm $A_1$ a total of $...
- 73
1
vote
1
answer
27
views
Show that $ O((8k)!^4 \cdot\mathrm{poly}(n))=e^ { O ( \sqrt n \cdot \log n ) } $ given $ k = O( \sqrt n ) $
I read this paper
looking for the best upper bound for computing the Homfly polynomial.
At the end the author makes a substitution which I would like to understand correctly. In Corollary 20 the ...
- 2,198
4
votes
2
answers
134
views
No Dijkstra and no BFS? What else is there?
So, this is the scenario I have a graph with 7 points (say A to G) all interconnected (full mesh), and I want the best path to traverse all points starting from A and ending on G, but there are a ...
0
votes
0
answers
36
views
In TSP where a modified triangle inequality holds, what is the approximation ratio of Christofides' algorithm?
In the metric TSP, we can use Christofides' algorithm to get a $\frac{3}{2}$-approximate solution. This is a consequence of the triangle inequality where $d_{ij} + d_{jl} \geq d_{il}$, that enables us ...
