Questions tagged [efficiency]

Using as few resources (e.g. time, space) as possible while solving a problem. Use this tag if your question is specifically about resource usage, not for generic algorithm questions that happen to mention running times.

Filter by
Sorted by
Tagged with
193 votes
10 answers
54k views

How can a language whose compiler is written in C ever be faster than C?

Taking a look at Julia's webpage, you can see some benchmarks of several languages across several algorithms (timings shown below). How can a language with a compiler originally written in C, ...
user avatar
54 votes
4 answers
8k views

Why polynomial time is called "efficient"?

Why in computer science any complexity which is at most polynomial is considered efficient? For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms ...
user avatar
  • 20.4k
52 votes
5 answers
52k views

Factorial algorithm more efficient than naive multiplication

I know how to code for factorials using both iterative and recursive (e.g. n * factorial(n-1) for e.g.). I read in a textbook (without been given any further ...
user avatar
  • 665
46 votes
6 answers
6k views

Dealing with intractability: NP-complete problems

Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?
user avatar
  • 561
34 votes
3 answers
64k views

Why is selection sort faster than bubble sort?

It is written on Wikipedia that "... selection sort almost always outperforms bubble sort and gnome sort." Can anybody please explain to me why is selection sort considered faster than bubble sort ...
user avatar
  • 481
34 votes
5 answers
62k views

Adding elements to a sorted array

What would be the fastest way of doing this (from an algorithmic perspective, as well as a practical matter)? I was thinking something along the following lines. I could add to the end of an array ...
user avatar
  • 1,113
30 votes
7 answers
6k views

Are algorithms (and efficiency in general) getting less important?

Since buying computation power is much affordable than in the past, are the knowledge of algorithms and being efficient getting less important? It's clear that you would want to avoid an infinite loop,...
user avatar
27 votes
2 answers
4k views

Efficient map data structure supporting approximate lookup

I'm looking for a data structure that supports efficient approximate lookups of keys (e.g., Levenshtein distance for strings), returning the closest possible match for the input key. The best suited ...
user avatar
  • 409
26 votes
3 answers
10k views

When is the AKS primality test actually faster than other tests?

I am trying to get an idea of how the AKS primality test should be interpreted as I learn about it, e.g. a corollary for proving that PRIMES ⊆ P, or an actually practical algorithm for primality ...
user avatar
  • 361
26 votes
3 answers
13k views

Retrieving the shortest path of a dynamic graph

I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is ...
user avatar
22 votes
7 answers
9k views

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

I am preparing for a coding interview and I can't really figure out the most efficient way to solve this problem. Let's say we have two arrays consisting of numbers that are unsorted. Array 2 ...
user avatar
21 votes
3 answers
12k views

What is the most efficient way to compute factorials modulo a prime?

Do you know any algorithm that calculates the factorial after modulus efficiently? For example, I want to program: ...
user avatar
15 votes
7 answers
13k views

Can we say DFA is more efficient than NFA?

I just started reading about theory of computation. If we compare which is more powerful (in accepting strings), both are same. But what about efficiency ? DFA will be fast compared to NFA, since it ...
user avatar
  • 1,443
15 votes
2 answers
539 views

Problems that feel exponential but are P

I'm trying to build a list of algorithms/problems that are "exceptionally useful", as in, solving problems that 'seem' very exponential in nature, but have some particularly clever algorithm that ...
user avatar
14 votes
2 answers
16k views

When can I use dynamic programming to reduce the time complexity of my recursive algorithm?

Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that ...
user avatar
  • 141
14 votes
2 answers
12k views

Are all context-free and regular languages efficiently decidable?

I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly $\mathrm{P}$). I perfectly understand that efficient problems are a ...
user avatar
  • 2,143
13 votes
2 answers
3k views

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

So merge sort is a divide and conquer algorithm. While I was looking at the above diagram, I was thinking if it was possible to basically bypass all the divide steps. If you iterated over the ...
user avatar
12 votes
3 answers
6k views

What data structure would efficiently store integer ranges?

I need to keep a collection on integers in the range 0 to 65535 so that I can quickly do the following: Insert a new integer Insert a range of contiguous integers Remove an integer Remove all ...
user avatar
  • 427
11 votes
3 answers
2k views

Is there any proof that quantum computers are more efficient than classical computers?

Shor's algorithm is often used as the argument. It can solve the factorization problem faster than any known algorithm for classical computers. Yet, we have no proof classical computers can't also ...
user avatar
  • 4,017
11 votes
2 answers
4k views

Dynamic programming with large number of subproblems

Dynamic programming with large number of subproblems. So I'm trying to solve this problem from Interview Street: Grid Walking (Score 50 points) You are situated in an $N$-dimensional grid at ...
user avatar
  • 349
11 votes
3 answers
1k views

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

One is required to find power (positive integer) of matrix of real numbers. There are lots of efficient matrix multiplication algorithms (e.g. some parallel algorithms are Cannon's, DNS) but are there ...
user avatar
  • 1,351
11 votes
3 answers
462 views

Notions of efficient computation

A polynomial-time Turing machine algorithm is considered efficient if its run-time, in the worst-case, is bounded by a polynomial function in the input size. I'm aware of the strong Church-Turing ...
user avatar
10 votes
1 answer
1k views

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

On an imperative programming language, let us consider the following program: ...
user avatar
  • 123
10 votes
3 answers
4k views

Is there an algorithm for checking if a string is a catenation of palindromes?

Is there a linear-time algorithm to check that a sequence of characters is a concatenation of palindromes? The only thing that comes to my mind is the naive solution: ...
user avatar
  • 3,610
9 votes
4 answers
919 views

Finding the two largest of five small integers as quickly as possible

I use a variation of a 5-cross median filter on image data on a small embedded system, i.e. x x x x x The algorithm is really simple: read 5 unsigned ...
user avatar
9 votes
3 answers
6k views

Maximum subset pairwise not divisible by $K$

I have a set of numbers, and want to calculate the maximum subset such that the sum of any two of it's elements is not divisible by an integer $K$. I tried to solve this problem, but I have found the ...
user avatar
  • 201
9 votes
2 answers
2k views

Looking for a set implementation with small memory footprint

I am looking for implementation of the set data type. That is, we have to maintain a dynamic subset $S$ (of size $n$) from the universe $U = \{0, 1, 2, 3, \dots , u – 1\}$ of size $u$ with operations ...
user avatar
  • 2,977
9 votes
1 answer
1k views

Given n strings, is one of them a substring of another?

Suppose we are given a collection of $n$ strings, $S_1,\dots,S_n$. I would like to know whether any of those strings is a substring of any other string in the collection. In other words, I'd like an ...
user avatar
  • 143k
8 votes
3 answers
839 views

How can I generate first n elements of the sequence 3^i * 5^j * 7^k?

How can I efficiently generate the first N elements of the sequence $3^i 5^j 7^k$, where $i,j,k \in \mathbb{N}$? I've googled around a bit and found the sequence in OEIS, but I don't really see a ...
user avatar
8 votes
4 answers
21k views

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

I need a data structure which can include millions of elements, minimum and maximum must be accesable in constant time and inserting and erasing element time complexity must be better than linear.
user avatar
8 votes
2 answers
3k views

Why is it most efficient to resize a dynamic array to 2 * array.length()?

By dynamic array, I mean an array that when it becomes full we replace it with a new array having greater capacity than the previous array. I read in a textbook that doubling the size of the array is ...
user avatar
8 votes
1 answer
569 views

Relaxed Bin Packing Problem

The problem I have is like this bin packing problem, but instead I have $n$ bins and a collection of items with discrete masses. I need to put at least $m$ kg of stuff in each bin. Is there an ...
user avatar
  • 201
8 votes
4 answers
417 views

Applying algorithms on large data

Is there any book or tutorial that teaches us how to efficiently apply the common algorithms (sorting, searching, etc.) on large data (i.e. data that cannot be fully loaded into main memory) and how ...
user avatar
  • 503
8 votes
0 answers
630 views

Chained operations on sequences with two operators

Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation? Can we learn from matrix chain multiplication? A generalization of matrix chain ...
user avatar
  • 6,091
7 votes
3 answers
472 views

When did polynomial-time algorithm become of interest?

I would like to understand why and when polynomial algorithms became of interest. When did people realize the role and importance of efficient versus non-efficient algorithms? Did that happen when ...
user avatar
  • 719
7 votes
3 answers
702 views

Can a Minimum Possible Efficiency be proven?

Given a problem, is it possible to prove what the best worst-case efficiency of an algorithm to solve this problem would be? For example, lets take the problem of sorting an array. Many of the ...
user avatar
7 votes
5 answers
10k views

Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent?

I fail to understand why cut off value would be system dependent, and not a constant. From Princeton University website Cutoff to insertion sort. As with mergesort, it pays to switch to ...
user avatar
7 votes
4 answers
5k views

How can a quadratic algorithm be faster than a linearithmic one?

I have to solve the following problem: Al and Bob are arguing about their algorithms. Al claims his $O(n\log n)$ time method is always faster than Bob’s $O(n^2)$ time method. To settle the issue, ...
user avatar
  • 259
7 votes
4 answers
1k views

Are there real lexers that use NFAs directly instead of first transforming them to DFAs?

I am taking the Coursera class on compilers and in the lesson about lexers it is hinted that there is a time-space tradeoff between using non-deterministic finite automaton (NFA) and deterministic ...
user avatar
  • 171
7 votes
2 answers
7k views

What are efficient data structures for inserting and accessing elements?

Is there a data structure to keep a list of elements (not necessarily sorted) that performs the Access (by index) and Insert operations in a reasonable asymptotic time? When I say "reasonable time", ...
user avatar
  • 215
7 votes
1 answer
1k views

Why choose D* over Dijkstra?

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From Wikipedia, I can understand the algorithm. What I do not understand is why I would use D* ...
user avatar
7 votes
1 answer
354 views

Travelling with the most efficient path

A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time. The problem is: you have to travel $1000$ km. The only gas ...
user avatar
  • 130
7 votes
2 answers
974 views

What is a good binary encoding for $\phi$-based balanced ternary arithmetic algorithms?

I've been looking for a way to represent the golden ratio ($\phi$) base more efficiently in binary. The standard binary golden ratio notation works but is horribly space inefficient. The Balanced ...
user avatar
  • 211
6 votes
2 answers
388 views

Difference between $O(n^2)$ and $O(m)$ for algorithms on graphs

Given a graph $G$ directed with n nodes and m edges, if an algorithm solves a problem $X$ on $G$ with a complexity $O(n^2)$, while an other algorithm solves same problem $X$ on $G$ but with ...
user avatar
  • 401
6 votes
1 answer
217 views

Is it possible to implement a dictionary with efficient access according to insertion order?

I am trying to build a generic data structure that needs to hold keys and values and in the same time keep track on the indices in which keys and values were put in, like arraylists do but in a ...
user avatar
  • 161
6 votes
2 answers
2k views

Data structure for A*'s "open" set

I'm looking at Wikipedia's pseudocode implementation of A* and found myself wondering about what they call openSet. That is, the neighbours we've seen, but not yet ...
user avatar
6 votes
1 answer
132 views

How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$?

Let $\mathbf{X}$ be a $n \times n$ matrix. Given that we can only keep $k$ rows ($k << n$) or columns of the matrix in memory, how can we compute $\mathbf{X}^T \mathbf{X}$ while minimizing the ...
user avatar
6 votes
1 answer
928 views

Would you ever use a skip list over a treap?

Skip lists are taught as a standard of the undergrad CS curriculum at many major universities. However, from my reading* I can't find any practical situation where you would use a skip list over a ...
user avatar
  • 828
6 votes
2 answers
3k views

Choosing the optimal radix/number-of-buckets when sorting n-bit integers using radix sort

This is a popular question: What is the most efficient (in time complexity) way to sort 1 million 32-bit integers? Most answers seem to agree that one of the best ways would be to use radix sort ...
user avatar
6 votes
1 answer
321 views

Radon transform for advanced 3d graphics and games?

The Radon transform is used to take 2d projections of an object and create a 3d representation. It seems like it would be possible to apply such a transform in 3d graphics in games (although possibly ...
user avatar
  • 171

1
2 3 4 5 6