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 ...
- 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 ...
- 237
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 ...
- 1,055
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, ...
- 945
3
votes
Accepted
An efficient way to find a pair of unrelated edges
This 2015 paper by Williams et al. considers induced subgraphs and shows how to find $C_4$ and co-$C_4$ in a graph $G$ time $O(\min\{n^\omega, m^{\frac{4\omega-1}{2\omega+1}}\})$, where $n$, $m$ are ...
- 29.5k
2
votes
Finding asymptotically tight upper bound of a recursion relation
Your upper bound is not tight. Let $n=5^k$, as in you question. You can upper bound your summation by
$$
\sum_{i=1}^{k} 5^i \cdot \log^2 5^{k-i} \le
6 \sum_{i=1}^{k} 5^i (k-i)^2 =
6 \cdot 5^{k} \...
- 29.5k
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 ...
- 13.4k
2
votes
Optimizing findMissingNumber algorithm to O(N)
Query the least significant bit (LSB) of all the numbers and split them into two sets $E, O$ where $E$ contains the even numbers (the least significant bit is 0) and $O$ contains the odd numbers.
Now ...
- 29.5k
2
votes
Accepted
How are pointers modeled on bit-based computer models?
It sounds like you're just asking for the definition of Random-access machine, which is similarly formal to Turing machines, but formally defines how to do "indexing" operations.
There's ...
- 945
2
votes
Accepted
Bound $T$ asymptotically tight | Recursive trees
We can directly approach this problem using the recurrence tree method. Let us now denote $1-\alpha$ as $\beta$ for notational clarity. For any constant $l\ge2$ we have, $\alpha^l+\beta^l < 1$.
...
- 565
2
votes
Bound $T$ asymptotically tight | Recursive trees
Using the Akra-Bazzi method we have that
$
\alpha^p + (1-\alpha)^p = 1
$
for $p=1$, and that:
$$
\int_1^n \frac{x^l}{x^{p+1}} \, \text{d}x =
\int_1^n x^{l-2} \, \text{d}x= \frac{x^{l-1}}{l-1} \,\bigg|...
- 29.5k
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 ...
- 8,248
2
votes
Run-time complexity of solving a system of integer linear equations
You can solve this in polynomial time by computing the Hermite normal form of $A$. This is the integer analogue of Gaussian elimination.
- 1,197
1
vote
Set partitions and integer partitions
It should help to see that if $(S_1, …, S_k)$ is a set partition for input $(X, n_1, …, n_k)$, then $(S_2, …, S_k)$ is a set partition for input $(X\setminus S_1, n_2, …, n_k)$.
Now you just need to ...
- 15.6k
1
vote
Run-time complexity of solving a system of integer linear equations
With an nxn matrix and an n by n vector, there is usually exactly one solution. So you find it and just check if it is all integers.
Now if the equations are not independent then you have none or ...
- 30k
1
vote
Time Complexity: Determining if a binary tree is balanced
Determining if a binary tree is balanced runs in $O(n)$, since we only need to traverse each node once, and moving from one node to another requires $O(1)$ moves.
However, since your code calculates ...
- 656
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
Finding asymptotically tight upper bound of a recursion relation
Given, $$T(n)=5T(\frac{n}{5})+\log^2(n)$$ compare with $$T(n)=aT(\frac{n}{b})+n^k\log^p(n)$$(By master theorem) where $a\geq1,b>1,k\geq 0$ and $p \in \mathbb{R}.$
Since $a> b^k$, $T(n) =\Theta(n^...
- 317
1
vote
Is "super-exponential" a precise definition of algorithmic complexity?
The term 'superexponential' is not a precise description of algorithmic complexity, but it always suggests a growth greater in order than a simple exponential function of form $b^n$ for some $b > 1$...
- 302
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$ ...
- 1,234
1
vote
Measuring time complexity in the length of the input v/s in the magnitude of the input
You are correct; time complexity in theoretical computer science is usually measured in terms of the size of the input1.
This imposes a wrinkle for working programmers using time complexity to reason ...
- 1,704
Only top scored, non community-wiki answers of a minimum length are eligible