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

260 questions
Filter by
Sorted by
Tagged with
0answers
143 views

### Calculating the classification threshold efficiently

I have a multi-label classification problem, in which each input sample has a set of zero or more output labels. I have a multi-class classifier which, for every input sample, returns a certain score ...
2answers
6k views

### Algorithm to add sum of every possible xor-sum sub-array

I participated in one algorithmic competition. I got stuck in one problem, I am asking the same here. Problem Statement XOR-sum of a sub-array is to XOR all the numbers of that sub-array. An array ...
2answers
726 views

### Enumerating weighted permutations in sorted order problem

Let $S$ be a set of $n$ integers. Consider the following weighted permutations problem. Let $m<n$ be an integer. What is an efficient algorithm to enumerate all subsets of $m$ integers of $S$ ...
2answers
241 views

### What do I need to know about algorithms?

Drawing from Are algorithms (and efficiency in general) getting less important?, I get that algorithms are more important than ever, but I need to know anything about them other than their ...
7answers
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,...
4answers
45k 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 ...
1answer
54 views

### Finding users covering a set x by x

I have a Set $S$ of objects, a set $U$ of users and a map $c: U \rightarrow S^{\prime}$, where $S^{\prime} \subset S$ and $\emptyset \notin S^{\prime}$. Every time I add a new entry to $c$, i.e. ...
1answer
96 views

### Calculate the number of elements after multiplying/adding two polynomials

Suppose I have two polynomials $f(x)$ and $g(x)$ and I somehow represent their coefficients. I have a couple of ways to hold a polynomial depending on how many significant coefficients the polynomial ...
3answers
5k 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 ...
2answers
514 views

### What is the impact of synchronisation overhead on parallel speedup? [closed]

When implementing a parallel version of an algorithm, what is the impact of synchronization delays on speedup efficiency? Does this depend on the platform used? Is coarse-grained parallelism better ...
2answers
6k 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", ...
3answers
2k views

### What is the most power/energy efficient sorting algorithm?

I am writing a Android phone application that needs to be very power efficient, and I would like to use the most power efficient sorting algorithm. I will implement it in C for extra power efficiency. ...
3answers
63k 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 ...
1answer
332 views

### Largest reported speedup for a parallel computation?

A parallel implementation of a computation is usually compared to a sequential version of the same computation. The ratio of the time taken by the sequential version to the time taken by the parallel ...
3answers
714 views

### Priority queue with ubounded number of elements (i.e., with dynamic storage)

I'm looking for a data structure that can work as a priority queue with reasonable maintenance complexities (like $O(\log n)$ for insertion and deletion) and that has a theoretical unbounded limit for ...
4answers
3k views

### What are flops and how are they benchmarked?

Apple has just proudly stated that their new mac pro will be able to give up to 7 teraflops of computing power. Flops stands for Floating Point Operations Per Second. How exactly is this benchmarked ...
0answers
659 views

### Why does Shellsort work well on Sorted and Reverse ordered lists?

I've ran some tests and found that Shellsort runs much faster on ordered and reversed lists compared to random lists and almost ordered lists. ...
7answers
15k views

### Explaining why FFT is faster than DFT for the general public?

How would you explain why the Fast Fourier Transform is faster than the Discrete Fourier Transform, if you had to give a presentation about it for the general (non-mathematical) public?
1answer
522 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 ...
1answer
603 views

### Optimized algorithm to compare templates of two websites

My task is to compare templates of two websites. I am ready with my algorithm. But it takes too much time to give a final answer. Here, "template" means the way any page presents its contents. ...
2answers
1k views

### How do we determine how much time a multi-tape DTM saves over a one-tape DTM?

Note: This is a part of a homework question Were asked to construct a multi-tape Turing Machine for language {$a^n b^n c^n \mid n \geq 0$} Then it says "Discuss how much time your machines saves ...
1answer
550 views

### Are genetic algorithms special instances of random search done in an unexpectedly short run-time? [closed]

I was wondering since randomness is embedded in genetic algorithms at almost every level, is there a really fine line between genetic algorithms and pure random search? Ever since I finished my ...
2answers
80 views

### Random file access in a block based file format

I am writing a program to store, retrieve and delete "blocks" of data of varying sizes. The way it currently works is by keeping a database storing the locations of the blocks and the locations of ...
1answer
6k views

### Complexity of algorithm inserting an element in a circular linked list at the front end

In a circular linked list, if an elements needs to be inserted at front [just before the node pointed by head], can be done in O(1) (see the answer here) But in a book currently, I have, it is ...
1answer
169 views

### A vector-like data structure with allocation table; O(1) indexing time required

I am a beginner in data structures and recently came across a vector implemented on an array, which is extended on demand. Of course the table cannot be extended "in place", we must allocate a new ...
4answers
744 views

### Speeding up a program solving Icosoku

I bought a great puzzle called Icosoku. Wikipedia describes it as: "The puzzle frame is a blue plastic icosahedron, and the pieces are 20 white equilateral-triangular snap-in tiles with black dots and ...
1answer
53 views

### Modeling timing characterists of an architecture

I am building a system and I have a couple of architectures in mind. I want to have an idea of which architecture is likely to be most performant (quickest). I can make different decisions like 1) ...
4answers
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 ...
3answers
3k 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: ...
7answers
12k 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 ...
2answers
208 views

### Which is more computationally efficient: multiplication or 0 padding?

On a PC I am implementing an algorithm in which a number from a look table will be chosen randomly, and will be multiplied by 1000 or 10000. Instead of multiplying by 1000 or 10000 I am thinking of ...
2answers
76 views

### Cache strategies, what reference article could I study?

So as to optimize an application, I must implement data caching: not to recompute some data - those heavy on cpu but that don't change often. When playing with the idea, I imagined something like the ...
1answer
252 views

### Regular vs LALR(1): what is faster

Supposing we have two grammars which define the same languge: regular one and LALR(1) one. Both regular and LALR(1) algorithms are O(n) where n is input length. Regexps are usually preferred for ...
1answer
694 views

### What sort of algorithm/communication model/data structure do collaborative real time editors use?

I am researching collaborative editing systems for some work, but so far my search is turning up blank. Collaborative real-time editing systems almost all have features like: Many users can edit the ...
3answers
12k 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 ...
1answer
432 views

### What are the effects of the alphabet size on construct algorithms for suffix trees?

For what size alphabet does it take longer to construct a suffix tree - for a really small alphabet size (because it has to go deep into the tree) or for a large alphabet size? Or is it dependent on ...
0answers
617 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 ...
1answer
494 views

### Implementing addition for a binary counter

A binary counter is represented by an infinite array of 0 and 1. I need to implement the action $\text{add}(k)$ which adds $k$ to the value represented in the array. The obvious way is to add 1, k ...
2answers
977 views

### Algorithm to pack any small boxes into a big box

I have a container with a certain dimension. A number of small boxes that may be different in size is to be packed into the container. How to arrange the small boxes such that the container contains ...
1answer
3k views

### Maximum Schedulable Set Zero-Lateness Deadline Scheduling

This is a homework problem for my introduction to algorithms course. Recall the scheduling problem from Section 4.2 in which we sought to minimize the maximum lateness. There are $n$ jobs, each ...
1answer
309 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 ...
1answer
179 views

### Time - Complexity Convex Optimization and Eigen Decomposition

Say I had the choice of choosing one out of the following two optimization problems which I could use to solve my problem. Which choice is the fastest? How much of a trade-off would it be? Is the ...
1answer
1k views

### Calculate storage requirements for a data set

I have a simple problem. I can't seem to even find the right search terms to get me pointed in the direction I need to be heading. I'm writing a bunch of integers to disk. Lot's of them. Starting ...
2answers
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 ...
4answers
383 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 ...
1answer
265 views

### How to compute linear recurrence using matrix with fraction coefficients?

What I'm trying to do is generate Motzkin numbers mod a large number $10^{14} + 7$ (not prime), and it needs to compute the $n$th Motzkin number as fast as possible. From Wikipedia, the formula for ...
1answer
825 views

### Running time of CDCL compared to DPLL

What's the complexity of Conflict-Driven Clause Learning SAT solvers, compared to DPLL solvers? Was it proven that CDCL is faster in general? Are there instances of SAT that are hard for CDCL but easy ...
2answers
875 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 ...
1answer
2k views

### Queue that can sort by multiple priorities?

I have a high interest in priority-queues (E.g., see my answers on: Does there exist a priority queue with $O(1)$ extracts?), and was wondering if there is a priority-queue or similar data-structure ...
1answer
128 views

### Algorithm to check the 2∀-connectness property of a graph

A graph is 2∀-connected if it remains connected even if any single edge is removed. Let G = (V, E) be a connected undirected graph. Develop an algorithm as fast as possible to check 2∀-connectness of ...