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
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
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 ...
Steven's user avatar
  • 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} \...
Steven's user avatar
  • 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 ...
orlp's user avatar
  • 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 ...
Steven's user avatar
  • 29.5k
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$.     ...
codeR's user avatar
  • 634
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|...
Steven's user avatar
  • 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 ...
Discrete lizard's user avatar
  • 8,248
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 ...
Alex Meiburg's user avatar
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.
Emil Jeřábek's user avatar
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 ...
Nathaniel's user avatar
  • 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 ...
gnasher729's user avatar
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 ...
Kenneth Kho's user avatar
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

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^...
S. M.'s user avatar
  • 317
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
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 ...
Ben's user avatar
  • 1,704
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$...
Ṃųỻịgǻňạcểơửṩ's user avatar

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