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

153 questions
Filter by
Sorted by
Tagged with
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 ...
• 300
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 ...
• 107
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. ...
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 ...
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 ...
35 views

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 ...
• 300
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). ...
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 ...
1 vote
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 ...
• 4,055
54 views

• 817