20 votes
Accepted

Measuring time complexity in the length of the input v/s in the magnitude of the input

You're not missing anything -- you are correct! Consider a loop that prints Hello World $n$ times, where $n$ is an integer, then by the same procedure as above, this algorithm would also be ...
Caleb Stanford's user avatar
10 votes

What is the name of this search algorithm?

I do not think there is a name for that particular algorithm, but I think it will achieve similar performance to much simpler parallel algorithms for this task. In general when designing parallel ...
nosyarg's user avatar
  • 232
9 votes

Measuring time complexity in the length of the input v/s in the magnitude of the input

@CalebStanford's answer is excellent, but just to add one point: There is a distinction between how many operations are needed and how many bits are needed (more for each number of many digits), and ...
J.G.'s user avatar
  • 237
6 votes
Accepted

Possible Mistake in Skiena's Algorithm Design Manual

You are totally right, though I think there is an easier proof: if $m = n$, then $mn-m^2 +m= m\notin \Omega(m^2)$. However, since the analysis is done when searching for a worst case, you could just ...
Nathaniel's user avatar
  • 15.6k
4 votes

What is the time complexity of this algorithm of finding all prime numbers?

The following complexity is not tight; however closeby: The complexity of the algorithm is at least $\Omega(n \sqrt{n}/\log^2 n)$ and at most $O(n \sqrt{n}/\log n)$. For any natural number $x$, the ...
Inuyasha Yagami's user avatar
4 votes

How to prove greedy algorithm is correct

Jeff Ericson in his "Algorithms" states three conditions: Greedy choice: There is an optimal solution that includes the choice the algorithm makes. Inductive structure: The smaller ...
vonbrand's user avatar
  • 14k
3 votes

Measuring time complexity in the length of the input v/s in the magnitude of the input

There are two good answers already, but there are two points that weren't touched on. One is that of output-polynomial time. A lot of theoretical CS concerns itself purely with decision problems, ...
Alex Meiburg's user avatar
3 votes
Accepted

What is the name of this search algorithm?

It's a parallel linear search, with an over-complicated way to divide up the array into a power-of-2 number of chunks. (Since you only split in half with multiple levels of recursion, instead of the ...
Peter Cordes's user avatar
  • 1,055
2 votes

How to prove greedy algorithm is correct

There is a very nice theory on when greedy algorithms work in general. It is based on the abstract concept of matroids. A detailed explanation is given by Jeremy Kun.
vonbrand's user avatar
  • 14k
2 votes

Justification for the properties of algorithmic recurrences in 'Introduction to Algorithms' (CLRS, 4e)

The 1st property is referring to the time needed by the recursive algorithm to solve a problem instance with size $n<n_0$. Under this case the algorithm can directly solve the problem, i.e. no ...
Russel's user avatar
  • 2,745
2 votes

How branching factor affects complexity of Monte Carlo Tree Search?

Monte-Carlo Tree Search is not an exhaustive search algorithm. It just does a certain amount of iterations, and then it is done. The branching factor has a (dramatic) influence on the size of the ...
orlp's user avatar
  • 13.4k
2 votes
Accepted

Question about step in proof that predecessor subgraph forms a breadth-first tree

Your update is correct. On first reading I thought it was wrong because distances can be negative. It's early here for me ... then I remembered that CLRS defines distance from $s$ to $v$ to be the ...
Nikolay's user avatar
  • 36
2 votes
Accepted

Prove that the number of comparisons between elements in binary heap build is at most (2n-2)

The first two proofs only work for a fully populated heap of height h, which contains n=2h-1 items. The third proof also works for partial heaps. Throughout this answer, i will use two functions ...
Rainer P.'s user avatar
  • 842
2 votes
Accepted

Prove the relation between space complexity and time complexity of the graph search which uses "the explored set"

The usage of "within" is a bit confusing, but I think it means the space complexity is never smaller than the time complexity divided by a factor of $b$. The space complexity of an algorithm ...
Discrete lizard's user avatar
  • 8,248
2 votes
Accepted

Find all the induced paths with a start vertex

Consider the following graph $G = (V, E)$ where: $V = \{v_0\}\cup \{u_1,…, u_n\}\cup \{v_1, …, v_n\}$; $E = \{\{v_0,u_1\}, \{v_0, v_1\}\}\cup \bigcup\limits_{k=1}^{n-1}\{\{u_k, u_{k+1}\}, \{u_k, v_{k+...
Nathaniel's user avatar
  • 15.6k
1 vote
Accepted

Why is the push operation in incrementally grown array stack is $O(n^2)$

The time for pushing in a stack of size $k$ is $O(k)$. Thus the cost of all of the pushes is: $$\sum_{k=1}^{n} k \ = \ \frac{n(n+1)}{2} \ = \ O(n^2) \ .$$
SilvioM's user avatar
  • 843
1 vote
Accepted

Explaination of incremental push's amortized time

It just means that the amortized time complexity is $O(n)$, amortized over $n$ pushes. The $[O(n^2)/n]$ indicates that the $O(n)$ amortized time comes from a total time complexity of $O(n^2)$ divided ...
SilvioM's user avatar
  • 843
1 vote

A $O(|E||V|)$ algorithm to determine if a graph is singly connected?

After doing more research, I believe the author of the preprint wasn't clear on the algorithm provided by CLRS. I think what CLRS meant is the following: for each $u \in V$ , run DFS-VISIT(u). In ...
Hugh Mann's user avatar
1 vote
Accepted

A $O(|E||V|)$ algorithm to determine if a graph is singly connected?

Note that the algorithm by CLRS runs DFS for each vertex separately. Therefore, for the case you mentioned, the algorithm declares the graph as non-singly connected when performing DFS starting from ...
Inuyasha Yagami's user avatar
1 vote

Solving Recurrence Relations with induction

Since you already noticed that the solution to D) appears to be $T(n) = H_n$, where $H_n = \sum_{i=1}^n \frac{1}{i}$ is the $n$-th harmonic number, why don't you use exactly this guess for the ...
Steven's user avatar
  • 29.5k
1 vote

Prove $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(n\log^2{n})$ using induction

Let $c$ be the constant for the $\Theta$ expression, and show that $T(n) \leq c n \log^2 n$. By induction, assume $n \geq 2$. $\begin{align} T(n) &= 2T(n/2) + cn \log n\\ &\leq 2(c \frac ...
Pål GD's user avatar
  • 16.1k
1 vote
Accepted

Prove $T(n)=10T(\frac{n}{3})+n\sqrt{n}=\Theta(n^{\lg_3{10}})$ using induction

I'll solve a simpler recurrence, $$T(n) = 4T(n/2) + n,$$ but the point is the same, namely that your induction hypothesis is too weak. We show something stronger: $T(n) \leq c \cdot n^2 - dn$ for some ...
Pål GD's user avatar
  • 16.1k
1 vote
Accepted

Is a predecessor subgraph always connected?

Let $s$ be your source vertex and let $d(v)$ denote the distance from $s$ to $v$. Let $v_1, \dots, v_n$ be the vertices of your graph in non-decreasing order of distances from $s$. You can show by ...
Steven's user avatar
  • 29.5k
1 vote
Accepted

Minimum number of comparisons to find $2$nd smallest element

Assume that all elements are distinct (if not, replace each element with a pair $(element, position)$ and perform the comparisons lexicographically) and consider a rooted binary tree $T$ with $n$ ...
Steven's user avatar
  • 29.5k
1 vote

Proving the correctness of a greedy algorithm for the Circular Scheduling Problem

Your algorithm is not correct. Consider intervals [1,7], [8, 14], [15, 21], [22,28], [13,16], [2,9], [3,10], [4,11], [17,23], [18,24], [19, 25]. Your algorithm chooses [13,16] first, as it only ...
Bernardo Subercaseaux's user avatar
1 vote
Accepted

Ways to speed up a Recursive Backtracking Algorithm

I think you pretty much got it there. There really aren't many ways to improve it, our best method is a slow one! (though our human brains instinctively would love to find something better for such a ...
Minko_Minkov's user avatar
1 vote

Parallel Algorithm Analysis: Loops

The work $W(n)$ is the total number of nodes in your computation graph and the span $D(n)$ is the number of nodes on the longest path of that graph. $T_P(n)$ is the runtime of the algorithm using $P$ ...
Gaslight Deceive Subvert's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible