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].

Filter by
Sorted by
Tagged with
-1 votes
0 answers
17 views

Algorithms & Datastructures: Depth-First Search (DFS) and Breadth-First Search (BFS) Space Optimizations [closed]

Problem I am currently digging deep into some optimizations on the classical iterative approaches to both DFS and BFS algorithms. The material I'm currently using at my University presents both ...
Michel H's user avatar
  • 300
0 votes
0 answers
22 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 ...
J3ck_Budl7y's user avatar
0 votes
1 answer
54 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. ...
A.V. Anderson's user avatar
0 votes
1 answer
19 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 ...
suryansh_shekahawat's user avatar
2 votes
0 answers
32 views

Applications of analytic combinatorics

At the beginning of "Analytic Combinatorics" by Flajolet and Sedgewick, there's some discussion about the "usefulness" of the book's techniques in the analysis of algorithms and ...
weekendwarrior's user avatar
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)...
Ariana's user avatar
  • 375
-3 votes
1 answer
60 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 \...
Liz's user avatar
  • 1
2 votes
0 answers
89 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 ...
eagle I 's user avatar
0 votes
6 answers
229 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 ...
spiros's user avatar
  • 157
3 votes
1 answer
70 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^{...
MM7654DDD's user avatar
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?
Holland Davis's user avatar
0 votes
0 answers
27 views

Testing a Pseudo-Random Number Generator Algorithm

I created a pseudo-random number generator that creates random bits from given numbers. For better visualization, suppose that we have inputs "a", "b", "ab", "abc&...
Severus' Constant's user avatar
1 vote
2 answers
58 views

Algorithm analysis - when to throw away terms?

In this algorithmic analysis of least squares regression, we throw away big-$O$ terms that will be dominated by the biggest, and keep only the dominant term. On the other hand, in this algorithmic ...
caitlin's user avatar
  • 125
2 votes
0 answers
50 views

Is there a notion of different level of asymptotic equivalence?

For example, consider $f(n) = n^3\;$ vs $\;g(n) = (n-2)^3$. These two functions are considered to be asymptotically equivalent $f(n)\sim g(n)$ since $\lim_{n\to \infty}\dfrac{f}{g}=1$. But $|f-g|$ ...
Leon Kim's user avatar
  • 475
1 vote
0 answers
43 views

How close to optimal would a Traveling Salesman solution of "Check the distance to all non-visited points, then go to the nearest one" be?

While obviously not optimal, I've usually found that such an "algorithm" is pretty close to the true shortest possible path, and is obviously runnable in polynomial time, with an O equal to ...
Arctic's user avatar
  • 11
1 vote
0 answers
101 views

2SUM variant with 2 arrays

I've been racking my brain trying to figure this out. I think I came up with a solution but its not elegant at all, I was wondering if any of yall could think of anything else. This is the problem <...
Steve Harrington2's user avatar
0 votes
1 answer
45 views

Convergence analysis and Lipschitz constant

I'm reading a paper where in the convergence analysis of the algorithm, they make the assumption that the gradient of the function is Lipschitz continuous with constant $L > 0$. Then, in the ...
Ki Chao's user avatar
  • 43
0 votes
1 answer
77 views

Complexity of recursion with floor division $f(N) = F(N) - \sum_{m=2}^N f \left(\left\lfloor\frac N m \right\rfloor\right)$

Often in computational number theory, to compute $f(N)$, there are identities like $$F(N) = \sum_{m=1}^N f \left(\left\lfloor\frac N m \right\rfloor\right) $$ where $F(N)$ is easy to compute, i.e. $O(...
qwr's user avatar
  • 10.7k
1 vote
1 answer
94 views

Big-O analysis of recurrence relation

I'm not sure if I should be posting this question here or under Stackoverflow, but given that it's algorithmic analysis, I figured Math was the right call. I have 2 functions that I'm trying to find ...
Kevin's user avatar
  • 29
0 votes
1 answer
37 views

Using Big Oh to prove $f(n)+k$ is $O(g(n))$

Let $f(n)$ and $g(n)$ be positive functions such that $f(n)$ is $O(g(n))$ and $g(n) \ge 1$ for all $n \ge 1$. Using the definition of “big Oh” show that $f(n) + k$ is $O(g(n))$, where $k > 0$ is ...
Robert Williams's user avatar
2 votes
1 answer
364 views

Time complexity analysis of Kruskal's Algorithm

Hello I have a doubt about the time complexity of Kruskal's Algorithm. Symbols: $E \implies$ Total number of edges in the graph $V \implies$ Total number of vertices in the graph $O \implies$ Big $O$ ...
Shobhit Tewari's user avatar
1 vote
0 answers
16 views

Computing the p-rank of Divisor class group for function field

In the context of my work, I am trying to develop an algorithm to factorize some operators on algebraic function fields of positive characteristic $p$. To this end I need to be able to compute ...
raphitek's user avatar
0 votes
0 answers
33 views

Approximation factor for TSP algorithm

The literature that I have reviewed shows examples of calculations of known approximation algorithms such as the Christofides' algorithm for the TSP. However, I have not been able to find information ...
Mathematician....'s user avatar
0 votes
1 answer
82 views

Can an algorithm prove that it produced its own output?

Apologies in advance for my ignorance. I am working on a research question in a different area, and it would be helpful to know the answer to the following question, or even a reference to any such ...
Ralph 's user avatar
  • 31
0 votes
1 answer
124 views

Prove correctness of algorithm that computes $\lfloor \sqrt{n}\rfloor$

I was looking in V. Shoup's book 'A Computational Introduction to Number Theory and Algebra' (freely available here). The exercise is as follows: As I'm not very familiar with proving correctness of ...
user avatar
3 votes
2 answers
116 views

$\Theta$-notation of the recurrences $T(n) = 3T(n/2 +1) + n$ and $T(n) = 4T(n/2)-4T(n/4)+1$ [closed]

(a) $T(n) = 3T \left ( \frac{n}{2} + 1 \right ) + n$ (b) $T(n) = 4T \left ( \frac{n}{2} \right ) - 4 T \left ( \frac{n}{4} \right ) + 1$ I am really stuck on these two recurrences and finding out ...
user123's user avatar
  • 33
0 votes
2 answers
59 views

$g(n)$ upperbounds $f(n)$ but graph shows otherwise

Given we have the following functions: $$f(n)=\log_{2}^{4}n$$ $$g(n)=2^{\sqrt{\log_{2}n}}$$ I've done the limit of f(n) over g(n), and found that g(n) is an upperbound of f(n) given the zero result: $$...
Stacking_Flow's user avatar
0 votes
1 answer
18 views

Generalized range check for cyclic array (using modulo)

I'm currently dealing with cyclic arrays in Algorithms & Data Structures and wanted to find a "clean" way using the modulo function to express whether an index is within a certain range ...
Michel H's user avatar
  • 300
0 votes
1 answer
65 views

Recurrence and Big-O - Question 1) T(n)=T(√n)+Θ(log(log(n)) and T(2)=0.

I'm trying to solve the recurrence. Runtimes and recurrence solutions. For initial conditions T(2) = 0, solve for; T(n)=T(√n)+Θ(log(log(n)) (recursive relation). ...
Aygen Ergen's user avatar
0 votes
1 answer
92 views

Amortized analysis insert operation on linked list required in O(1) amortized

Having the following operation that should be implemented using sorted linked list: Insert(x): insert element x to the data structure and delete all keys smaller than x. (x is a real number) the ...
Baseel Kayal's user avatar
1 vote
0 answers
148 views

Efficiency of RREF algorithms

Compute the RREF of the following matrix :$$\begin{bmatrix}1&-1&2&-3&7\\4&0&3&1&9\\2&-5&1&0&-2\\3&-2&-2&10&-12\end{bmatrix}$$ My friend ...
DatBoi's user avatar
  • 4,055
0 votes
0 answers
54 views

Looking for proof of linearity: the sum of big-Theta is big-Theta of the sum.

I'm working on problems relating asymptotic notations. And I stumbled on this easy-looking statement, which asserts that with $S \subseteq \mathbb{Z}$, we have $$\sum_{k \in S} \Theta(f(k)) = \Theta\...
MINH NGUYỄN HỒNG's user avatar
0 votes
1 answer
47 views

Minesweeper sparsity and information processing

I've noticed while playing Minesweeper that when I have too few bombs, I get very easy to play games. In other words, I get games that can be solved with very simple algorithms. When I play games with ...
Joemoor94's user avatar
2 votes
0 answers
23 views

Pseudopolynomial running time for small input

I think that I generally understand the concept of pseudopolynomial running time for large input: e.g. An algorithm that checks whether a given natural number $n$ is prime by testing wheter it is ...
willwissen's user avatar
1 vote
0 answers
76 views

Deriving time complexity of Union-Find using only path compression

For the Union-Find algorithm, I've read that using path compression alone gives a worst-case running time of $O(n+f\cdot(1+\log_{2+\frac{f}{n}}(n)))$ for a sequence of $n$ MakeSet operations (and ...
Hugh Mann's user avatar
0 votes
0 answers
52 views

Help understanding if $f(n)=\theta(g(n))$?

I'm being asked to evaluate if $f(n)$ is a member of $\theta(g(n))$. $𝑓(𝑛) =(4 × 𝑛)^{150} + (2 × 𝑛 + 1024)^{400}\,$ vs. $\,𝑔(𝑛) = 20 × 𝑛^{400} + {(𝑛 + 1024)}^{200}$ From what I understand, we ...
Jean-Paul Azzopardi's user avatar
1 vote
0 answers
139 views

Average time complexity of insertion sort in Rosen's Discrete Mathematics and Its Applications

I came across the following average-case time complexity analysis for the insertion sort algorithm on page 483 of "Discrete Mathematics and its Application" by Kenneth Rosen: Average-Case ...
user51462's user avatar
  • 673
1 vote
1 answer
58 views

Asymptotic Analysis prove that [closed]

For $n \geq 1$, consider the following recurrence relation $$T(n) = \log2 n + T(n1/3).$$ Prove that $$T(n) = O(\log_2 n)$$
Lundrim Alla's user avatar
0 votes
0 answers
45 views

Proof that any node of rank $r$ has at least $2^r$ descendants implies that every node has rank at most $\lfloor \lg(n)\rfloor$

In the context of the union by rank algorithm (with respect to the disjoint-set data structure), I've read that since any node of rank $r$ has at least $2^r$ descendants, it follows that every node ...
Hugh Mann's user avatar
0 votes
1 answer
169 views

Question about proof that every node has rank at most $\lfloor \lg(n)\rfloor$

I have a question about a proof I found for the following claim in the context of the union by rank algorithm with respect to the disjoint-set data structure: Claim: Prove that every node has rank at ...
Hugh Mann's user avatar
0 votes
2 answers
58 views

Solve a non-linear recurrence analytically

I have a recurrence: $$f_n = 1/n*f^2_{n/2} + n $$ where $T(1)=2$ and $n$ is a power of 2 and I want to solve it analytically not asymptotically. I cannot find bibliography for such type where a $T(n)$ ...
tonythestark's user avatar
-1 votes
1 answer
60 views

How might we formally define the concatenation of two strings?

Below we offer some definitions of string. How would you mathematically define the concatenation of strings? The $\mathtt{HELLO\ WORLD}$ Example $“\mathtt{HELLO}” + “\mathtt{\ }” + \mathtt{WORLD}” = ...
Toothpick Anemone's user avatar
1 vote
0 answers
172 views

How to derive time complexity of the Recurrence Relation - T(n,m) = T(n-1,m) + T(n,m-1) + c

I know that, T(n,m) = T(n-1,m) + T(n,m-1) + c it's the recurrence equation of Longest Common Subsequence algorithm. And the time complexity of the LCS in case of recursive method is O(2^n+m). The base ...
Samiddha 's user avatar
1 vote
1 answer
158 views

Is it possible that matrix multiplication can be performed in $O(n^{2+\epsilon})$ operations but not $O(n^2)$?

The Wikipedia article on the computational complexity of matrix multiplication shows that the fastest known algorithms have gone from $O(n^{2.8074})$ in 1969 to $O(n^{2.37188})$ in 2022. I wonder if ...
WillG's user avatar
  • 6,605
0 votes
0 answers
40 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 ...
Michel H's user avatar
  • 300
0 votes
0 answers
220 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 ...
Anton Shcherbinin's user avatar
0 votes
0 answers
61 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 ...
supernal-hades's user avatar
0 votes
1 answer
96 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 ...
Toothpick Anemone's user avatar
0 votes
0 answers
36 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(...
wintermute's user avatar
1 vote
1 answer
37 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}$; ...
Boy's user avatar
  • 25