# 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
Filter by
Sorted by
Tagged with
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
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
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 ...
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 ...
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 ...
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 ...
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(...
1 vote
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
209 views

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 ...
72 views

...
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 ...
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
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 ...
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 vote
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 ...
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 ...
1 vote
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
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 ...
84 views

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)\,$? ...
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
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
82 views

• 73
1 vote
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
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 ...