Skip to main content

# Tag Info

## Hot answers tagged efficiency

31 votes
Accepted

### One element that differs in two arrays. How to find it efficiently?

I see four main ways to solve this problem, with different running times: $O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes ...
• 3,734
29 votes
Accepted

### Can the "divide" step in a merge sort be avoided?

The confusion arises from difference between the conceptual description of the algorithm, and its implementation. Logically merge sort is described as splitting up the array into smaller arrays, and ...
• 479
18 votes
Accepted

### What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?

It's called "loop fusion". It's often more efficient, in the sense of doing more work per loop iteration and sometimes (as you say) other advantages. On the other hand, the fused loop in ...
• 22.3k
16 votes

### One element that differs in two arrays. How to find it efficiently?

The $\Theta(n)$ difference-of-sums solution proposed by Tobi and Mario can in fact be generalized to any other data type for which we can define a (constant-time) binary operation $\oplus$ that is: ...
• 2,170
15 votes
Accepted

### Maximum subset pairwise not divisible by $K$

Indeed there is a linear time algorithm for this. You only need to use some basic number theory concepts. Given two numbers $n_1$ and $n_2$, their sum is divisible to $K$, only if the sum of their ...
• 1,944
15 votes

### One element that differs in two arrays. How to find it efficiently?

I'd post this as a comment on Tobi's answer, but I don't have the reputation yet. As an alternative to calculating the sum of each list (especially if they are large lists or contain very large ...
• 411
14 votes

### One element that differs in two arrays. How to find it efficiently?

Element = Sum(Array2) - Sum(Array1) I sincerely doubt this is the most optimum algorithm. But it's another way to solve the problem, and is the simplest way to solve it. Hope it helps. If the number ...
• 1,617
11 votes

### Can the "divide" step in a merge sort be avoided?

I guess what you mean is the bottom-up implementation. In the bottom up implementation you start from single cell elements an move upward by merging elements into larger sorted lists/arrays. Just ...
• 9,837
7 votes
Accepted

### Is closed form of summation less costly?

I cannot imagine there exists an internal representation of multiplication on any machine that does not involve repeated addition. Try being more imaginative. I'm pretty sure that you were taught at ...
• 81.9k
7 votes
Accepted

• 30.6k
5 votes
Accepted

### Efficient algorithm for finding weakly connected components

Replace every directed edge $u \to v$ with an undirected edge $(u,v)$. Now use any standard algorithm for finding connected components in the resulting undirected graph. One standard approach for ...
• 162k
5 votes
Accepted

### Data structure for A*'s "open" set

I think I never heard the term "Open Set" as we usually call it "OPEN list" (and by convention we use upper-case letters). I mention this to highlight the fact that this structure is closer to a list ...
• 3,463
5 votes

### Problems that feel exponential but are P

For me all classic and the more recent more efficient algorithms to verify or find a minimum spanning tree (MST) of a connected edge-weighted graph are good candidates. Many of these algorithms are ...
• 39.1k
5 votes

### Data structure for finding max, inserting and deleting in O(1) and O(n) space

Suppose we have such data structure. We can find in $O(1)$ the max, delete the max in $O(1)$ and repeat it $n$ times. Hence, we can sort $n$ numbers in $O(n)$. Therefore, constructing such data ...
• 3,572
4 votes

### improving java 8's implement to hash map using avl tree

This page on Oracle's website says: The alternative String hash function added in 7u6 has been removed from JDK 8, along with the jdk.map.althashing.threshold system property. Instead, hash bins ...
• 3,128
4 votes
Accepted

• 5,479
3 votes

### Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

If by sequential you mean multiplying $m$ times, the $\log m$ solution of initially only calculating the relevant powers of $2$ (a.k.a Exponentiation by squaring) is clearly better for large $m$. ...
3 votes

### Is a TM that is simulated by a universal TM theoretically inherently slower than the TM itself?

No. There is no such proof. There exists a universal Turing machine $U$ and a machine $M_0$ such that $U$ simulating $M_0$ is faster than running $M_0$ directly. For instance, $M_0$ might implement ...
• 162k
3 votes

### Non-recursive (iterative) DFS with $O(n)$ size stack

You can keep only the topmost copy of a node on the stack: ...
• 5,951
3 votes

### Which data structure to use for accessing min/max in constant-time?

You should look into https://en.wikipedia.org/wiki/Van_Emde_Boas_tree. It comes with some compromises, mostly your elements need to be integers and memory consumption may be high (but may be way lower ...
• 31

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