# Tag Info

## Hot answers tagged runtime-analysis

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
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
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

• 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
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

### 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,196
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

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 ### 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 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 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\$...

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