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].
155
questions
0
votes
1
answer
65
views
Find the dominating term
I know that, $$a+b=\Theta(\max\{a, b\}).$$
I need to understand the dominating term in this expression,
$$\mathcal{O}(m^{\frac{2}{3}}n^{\frac{2}{3}}+m+n).$$
We know that,$$m^{\frac{2}{3}}n^{\frac{2}{...
- 303
1
vote
1
answer
24
views
Shortest path through vertex in weighted graph (Proof)
I'm currently studying several classic graph algorithms for shortest paths (Dijkstra, Bellman-Ford, etc.) and came to the following problem:
Problem
We have $G:=(V,E,\omega)$, a weighted, connected, ...
- 342
1
vote
0
answers
40
views
Feeling this proof that $\log_b(n)$ is $O(n)$, where b is any positive real number $\neq 2$, has an error.
From Rosen's Discrete Math textbook, I feel the part of the proof where they say
$$\log_b n = \frac{\log_2 n}{\log_2 b} < \frac{n}{\log_2 b}$$ where $b$ is any positive number not equal to $2$ is ...
- 883
0
votes
0
answers
33
views
Value range of dual variables in Jonker-Volgenant algorithm for solving linear assignment problem
In A shortest augmenting path algorithm for dense and sparse linear assignment problems an algorithm for the Linear Assignment Problem is given, with a $O(N^3)$ time complexity (where $N$ is the "...
- 161
0
votes
1
answer
43
views
Is there a closed form method of expressing the *content* of integer partitions of $n$?
I know that the question of a closed form for the number of partitions of $n$, often written $p(n)$, is an open one (perhaps answered by the paper referred to in this question's answer, although I'm ...
0
votes
2
answers
70
views
0
votes
0
answers
25
views
Proving inequality $y_0 \leq \dots \leq y_n \leq y_{n+1} \leq \sqrt{a} \leq \dots \leq x_{n+1} \leq x_n \leq \dots \leq x_n$
I want to calculate $\sqrt{a}, a \in \mathbb{R^+}$ with the following algorithm:
$y_n = \frac{a}{x_n}$, $x_{n+1} = \frac{y_n+x_n}{2}, n=0,1,\dots,$,
with a start value $x_0 \geq \sqrt{a}$.
Now there ...
- 119
0
votes
1
answer
63
views
Impossible Rubik's cube position (2 corners swapped!) [closed]
Left side, white up, Red, green, white corner swapped with Red, blue, white corner
Right side, white up, Red, blue, white corner swapped with Red, green, white corner
Right, Down, Back view of cube.
...
0
votes
1
answer
23
views
Is the Asymptotic complexity of the find max algorithm O(n) or O(n^2)?
Algorithm pseudocode:
1 def find max(data):
2 biggest = data[0] # The initial value to beat
3 for val in data: # For each value:
4 if val > biggest # if it is greater than the best ...
0
votes
0
answers
35
views
What's the time complexity of $g(1, n)$?
Let $f:N\rightarrow N$ and for all $i$ we have $f(i)\in \Theta(\sqrt i)$. For all $i, j$ such that $1\le i\le j\le n$ we define
$$g(i, j)=\begin{cases}f(i)& i=j\\\max_{i<k\le j}\{g(i,k-1)+g(k,j)...
- 375
-3
votes
1
answer
67
views
Is my proof wrong for: $n^k \in O(2^n) \text{ for any constant } k$ [closed]
I tried to prove this the following way, but not sure if this is correct?
$n^k \leq c \cdot 2^n$
$\log_2(n^k) \leq \log_2(c \cdot 2^n)$
$\log_2(n^k) \leq \log_2(c) + \log_2(2^n)$
$\log_2(n^k) \leq \...
- 1
2
votes
0
answers
91
views
An efficient algorithm for finding the generators of the unit group of $\mathbb{Z}[\zeta_p] $ (ring of cyclotomic integers, where p is a prime)
The group of units of $\mathbb{Z}[\zeta_p]$ has a finite number of generators. I am aware there are algorithms that can find these generators but they don't seem to be that efficient. I was wondering ...
- 95
0
votes
6
answers
239
views
Given recursive formula $a_n = 2a_{n-1}+1$, show $a_n = 2^n -1$ [closed]
I came across a recursion homework problem for a graduate algorithms class while looking at recursive algorithms.
We are given a recursive formula for a recursive algorithm that gives the total number ...
- 157
3
votes
1
answer
73
views
Solving the recurrence equation : $T(n) = 2T(n/2) + n^2$
Where $T(1)=1$ and assuming that $n=2^k$ and that $k\ge 0$ and that the Master Theorm can't be used.
What I tried:
$T(n) = 2T(n/2)+n^2$
Following backwards substitution to get a pattern:
$T(2^k)=2T(2^{...
- 31
0
votes
0
answers
10
views
Number of elementary binary operations (EBO's) required for Long multiplication in binary
How do they get the total of $≤2kl$ EBOs? Shouldn't it require $kl+k(l-1)=2kl-k$ EBOs? And where does the upper bounding "$≤$" come from?
- 137