# Tag Info

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 ...
• 7,068

### 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 ...
• 232

### 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 ...
• 237
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 ...
• 15.6k

### 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 ...
• 6,157

### 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 ...
• 14k

### 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, ...
• 945
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 ...
• 1,055

### 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.
• 14k

### 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 ...
• 2,745

### 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 ...
• 13.4k
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 ...
• 36
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 ...
• 842
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 ...
• 8,248
Accepted

• 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 ...
• 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 ...
• 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$ ...
• 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 ...
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 ...
• 164
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$ ...

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