Questions tagged [algorithm-analysis]

Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage. Use the [runtime-analysis] tag for questions about the runtime of algorithms.

1,948 questions
Filter by
Sorted by
Tagged with
307 views

Understanding a summation notation. Sum(j=2 to n) j - 1

I have been reading analysis of insertion sort in the "Introduction to algorithms" and faced a problem with understanding a specific summation notation when the worst case occurs. I know how ...
1 vote
123 views

Proof of approximation ratio for approximate triangle inequality version of k-center

Consider the standard $k$-center problem i.e find $k$ disks of radius $r$ that cover all points in a point set $P$. This problem has a well known greedy 2-approximation algorithm where you (...
• 190
1 vote
90 views

Why does it take O(n!) time to specify a canonical ordering for learning flatten adjacency matrices/graphs?

I was reading a paper for learning graphs (paper is GraphRNN) and it says in section 2.2 (emphasis by me): Vector-representation based models. One naive approach would be to represent G by flattening ...
• 2,950
208 views

How to prove the my greedy algorithm for placing guards?

Given $n$ images placed in indexes $x_1 < x_2 < ... < x_n$ and an endless number of guards, where each guard if placed in index $y$ can protect $[y-0.5,y+1]$. I want to protect all images ...
• 13
283 views

an algorithm to find the shortest path between two vertices whose weight is divided by 3?

I am trying to think of an algorithm such that giving a graph $G(V,E)$, and a weight function $w\colon E \to \mathbb{N}_+$ (which means giving every edge in the graph a positive weight), and a source ...
109 views

Can the worst-case analysis of $f(n)$ be $\Omega(g(n))$ but not $O(g(n))$?

I am struggling to wrap my head around using $\Omega$-notation to describe worst-case running time of an algorithm, or $O$-notation to describe the best-case running time. Specifically, I struggle to ...
• 101
1 vote
633 views

How to solve $T(n)=4T(\sqrt{n}/3)+(\log n)^2$ with the master theorem?

Can somebody help me with this recurrence please? $T(n)=4T(\sqrt{n}/3)+(\log n)^2$
521 views

$(\log n)^{\log n}$ lower-bound and upper-bound

we know that $n \geq \log{n}$ however I understand that $(\log n)^{\log n}$ grows faster than $n$. I have been trying to prove this however I can't seem to figure it out.
184 views

Count Sketch probability bound

I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
183 views

Quicksort: Probability of an element being compared to fewer than $k$ pivot elements

Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements. Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$. Furthermore, ...
42 views

Recursive approach of longest common subsequence

I tried to solve Longest common subsequence problem using recursion, however as I later discovered, my thinking approach was wrong. I took 2 strings say s1 and s2 with lengths l1 and l2, s1="...
249 views

Proof of Correctness : Arranging the sheep

I've come across a question in Codeforces contest 719(Div - 3). The problem goes like this : I was able to solve the problem by using another approach but had to use 4*n auxiliary space, where n is ...
846 views

recursive algorithm to sort children and parents based on value

Edit: I dont have CS background and I'm still studying Algorithms, so any help will count! I met this algorithm while I was in interview, I didn't know what category it falls in, and hence I was ...
177 views

Sorting by repeated reversal

Let $A$ be an array of $n$ integers containing the numbers $\{1, 2, \dots , n\}$ in some arbitrary order. For integers $i$ and $j$ such that $1 ≤ i < j ≤ n$, let $\mathrm{Reverse}(A, i, j)$ be a ...
• 157
24 views

How would the classes of regular, context-free, decidable, and Turing-recognizable languages relate to each other

I'm a bit confused as to how they relate to each other. I think I understand them individually but not sure how they would relate.
903 views

sum of array with O(1)

I have an array of n elements. Smallest element that exists in the array is x and the largest element is x+n. None of the numbers between x to x + n is missing from the array. i need an algorithm to ...
123 views

How to show working for summing of Big O notation

The equation below is intuitively correct, but how do you show that this is actually the case? What is the working out needed? $$\sum_{i=1}^{n-1}O(\lg n)=O(n\lg n)$$
• 113
82 views

Undecidable or Decidable

In a typical data structures class, we look at a variety of problems: finding an element in a list, sorting a list, balancing a binary search tree, finding the shortest paths in a graph, etc. Would ...
74 views

What is the difference between designing an algorithm that solves a problem and creating a TM that decides a language?

Question: What is the difference between designing an algorithm that solves a problem and creating a Turing machine that decides a language? A turing machine "decides" the language if it &...
146 views

Why do researchers only count the number of multiplications when analyse the time complexity of Matrix Multiplication?

In this article about the recent breakthough in Matrix Multiplication, it quotes Chris Umans's words: Multiplications are everything. The exponent on the eventual running time is fully dependent only ...
• 632
367 views

Average number of comparisons for a successful search of a prime number in a binary search tree

A binary search tree is constructed by inserting the following value sequentially: $$3, 9, 1, 6, 8, 7, 10, 4, 2, 5$$ Let $p_v$ be the probability to search for the value $v$ in the binary search tree (...
232 views

182 views

Average case analysis by key comparisons of Max Sort

I'm having trouble approaching this average case analysis in terms of key comparisons. The pseudo-code is as follows: ...
424 views

How to find the Expected height of a randomly built binary tree

I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or ...
1 vote
76 views

Can somebody please explain what are these variables doing here?

I have this algorithm: I understand overall what's happening here, we're shrinking the blossoms (odd cycles) to end up with a bipartite matching problem, and then opening them again to get a maximum ...
• 121
19 views

Computer Science [duplicate]

I am trying to solve the following problem to find big-theta. I am having a lot of trouble, if anyone can help! T(n)=8T(√n)+log^2(e^n)? The logarithm is base 2 and is squared.
471 views

How can we find the number of pairs of intersecting ranges on a circular number line?

I recently thought of and managed to solve this algorithmic problem: On a infinite 1-dimensional number line, we have N ranges specified by two distinct integers <...
67 views

substitution method - proving karatsuba algorithm is not O(n)

I want to prove that $T(n) \neq O(n)$ for the Karatsuba algorithm, which has the following recurrence:  T(n) = \begin{cases} k_1, & \text{if $n$ = 1} \\ 3T(n/2) + k_2n, & \text{if $n \gt$ 1} ...
• 101
1 vote