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

232 questions
Filter by
Sorted by
Tagged with
59 views

### Add edges to undirected graph to make connected and minimize longest path

I am trying to find an efficient algorithm to solve to following problem: Given an undirected disconnected graph, I want to add as few as possible edges to make to graph connected while minimizing the ...
37 views

### Is it true that for every genetic algorithm there exists a non-genetic algorithm that achieves the same results more efficiently?

And if it is not true, what are the problem classes or characteristics for which genetic algorithms are superior?
31 views

### Least computationally expensive bitwise addition

I am familiar with the oft-cited method of bitwise addition using XOR and left shift for the carry, applied recursively. I was wondering if this is the least computationally expensive way to achieve ...
182 views

### Algorithm for detecting overlaps

This is a real-world application, not a student assignment. Suppose a list of events of that have startTime and endTime, and ...
60 views

### Peculiar MCMC sampling problem

I have two random variables, X and Y, and Y is a positive real number. I can sample from $p(y|x)$, but I need to sample from $p(x)$, which I know to be proportional to $\frac 1 {E[y|x]}$. I could ...
55 views

### Figuring out when one algorithm will be slower than another algorithm [closed]

I'm studying for a computing exam and came past the following question on a past paper and need help with it. When would algorithm A be slower than algorithm B? Demonstrate your answer with the help ...
114 views

### Shortest path in a incomplete graph

I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. ...
133 views

### BigO time complexity of 3 nested for loops

I'm debating with a friend whether a particular function I wrote is $O(N^3)$ or $O(N \times M \times X)$ I believe it is the latter since all 3 variables differ in size. $N = 100, M = 50, X = 10000$ ...
67 views

### Calculating all products of $n-1$ factors when given $n$ factors

Let's assume we have an operator $$\times: E^2\to E$$ of which we merely know that it is associative. Let's say a multiplication $e\times f$ always takes up a time of $M$ for all $e, f\in E$. We're ...
48 views

### How much does C# gain from its value types

C# makes an distinction between value types and reference types contrast to Java where all (except primitives types) are of reference semantics. The design decision, as I understand it, is mainly to ...
80 views

### In which order to solve subproblems when using memoization?

I am currently trying to solve a task with memoization. I have following recursion: A (i, j) = f( A (i, j-1), A (i-1, j-1), A (i-1, j + 1) ) I am not sure in which order the sub-problems should be ...
155 views

### Efficient data structure handling insert(number) and find(sum) returning pair a,b such that a + b = sum

There are two operations as follows: insert(num): insert num into the data structure. find(sum): return a pair(a, b) ...
56 views

### MergeSort k arbitrary words in linear time

Given $k$ arbitrary words, such as $\{\text{"fjqke"}, \text{"gbqig"}, \text{"a"}\}$, is there a way to mergesort these words in linear time so that the final output would be "abefgggijkq"? I tried to ...
113 views

### Efficient algorithm to determine if a lambda calculus term is equivalent to one without a given free variable

Consider the following problem: given a lambda calculus term $t$ and free variable $v$ determine whether $\phi(t,v)$, where $\phi(t,v) := \exists t'. t' \equiv t \land v \notin FV(t')$. This problem ...
56 views

### Is there a running hash algorithm that can efficiently handle arbitrary updates to a file's contents?

This question is about file-hashing/fingerprinting algorithms (similar to SHA-1 and MD5 and so on). Those algorithms are handy ...
66 views

### “Ways to make change for a dollar”: How to optimize with constraints

I'm working on an algorithm that takes a number of unit coins ([1, 2, 5, 10] for example) and a certain amount of money (13 in this case), and figures out how many ways there are to provide change for ...
194 views

### Longest substrings of common length with the same parity

Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions: length of both $A$ and $B$ is equal to $x$; sum of ...
144 views

### Finding duplicates in a stream of numbers

This is an interview question. Say you have a function foo() which returns some integer. You need to write an algorithm that does the following: (...
51 views

### Number of steps in worst Case

we have to run a song on a Walkman,for that we need 2 full batteries.Let s say we have a mixed set of 30 batteries (15 are emtpy and and 15 are full) and then only way to test if the battery full or ...
137 views

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

This is an interview question. I need to implement a data structure that supports the following operations: Insertion of an integer in $O(1)$ Deletion of an integer (for example, if we call delete(7),...
240 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 ...
55 views

### Why does parallelising slow down this simple problem against looping through all the data?

I've been using multiprocessing and parallelisation for the first time this week on a very large data set using 32 CPUs. I decided to explore it for a smaller task just to see if I could learn ...
40 views

### Efficiently find elements which are out of place in an otherwise sorted list

I have some data that includes two columns for dates, and I want to retrieve - based on these two columns - all the instances where an illegal operation has occured. An operation is illegal if the ...
90 views

### Linked List in Maximal Scoring Subsequences Algorithm

For a project, I'm implementing the All Maximal Scoring Subsequences algorithm. In the analysis portion of the paper, it describes an optimization that makes the algorithm run in linear time. Namely, ...
133 views

### Will we ever achieve a $O(n)$ general purpose sorting algorithm (or at least better than $O(n\log(n)))$?

I've been thinking about this question ever since I learnt about the $O(n\log(n))$ sorting algorithms such as MergeSort, QuickSort (average case is pretty much worse case with a good choice of a pivot)...
309 views

### Is there a more efficient stability index algorithm?

I have this assignment for a class and we're beginning to learn time complexity. I have to find create a Java program that finds the stability indices of an array. Stability index being defined as a...
261 views

### How would the use of an external lookup table affect file compression?

It occurred to me that, the way compression essentially works, is that you have a mapping of long patterns to short patterns, which you replace one way to compress and the other to decompress. My ...
802 views

### What are efficient data-structures for insert/delete by index?

First of all, a definition of the operations: Insert by index: insert element e at index n, increasing the index of all ...
40 views

### Fast computation of k-fibonacci numbers

Let's define the sequence of $k$-Fibonacci numbers as $$F_i = 2^i, ~~ 0 \leq i \leq k-1$$ $$F_i = F_{i-1} + \dots + F_{i-k}, ~~ i \geq k$$ I have a problem which requires to compute $n$-th $k$-...
54 views

### Counting restricted partitions

Given positive intgers $N$ and $S$ i need to count in how many ways $N$ can be decomposed as sum of $S$ positive integers not greater than $\frac{N}{2}$:  N = x_1 + \dots + x_S, ~~~~ 0 \leq x_i \leq ...
160 views

### Efficient bucketing of numbers

Assume we have a sorted list of n numbers, I want to map those numbers to m buckets or clusters. For each bucket the average of all numbers in that bucket will be computed. The task is to find a ...
35 views

### Computing the shortest path in a labyrinth

I'm currently trying to map how to make a good algorithm that won't have issues to find the shortest path. The labyrinth consists of an X and Y dimensions as input; However, the labyrinth will ...
51 views

### Is this graph algorithm more efficient?

Suppose we are given a digraph A. We need to calculate its connectivity digraph B. I conceived two algorithms: 1. Set X = A. Loop Set Y = X*A united with identity Stop the loop if Y = X Set X = Y ...
2k views

### Efficient point grouping algorithm

I'm trying to find a good solution to the following problem: Given a set of 3d real number coordinates inside a cube, I want to group them into containers. The containers should contain all elements ...
143 views

### Most efficient unification algorithm?

I've been trying to find the most efficient unification algorithm by following reference chains on the Wikipedia article on unification. As far as I can tell, the fastest one is the one presented in "...
35 views

### Are their problems that we can not even approximate efficiently?

Most hard problems can either be solved efficiently in average time, or an approximation can be efficiently found. Are there any natural problems for which this is not the case? In particular, is ...
40 views

### Is closed form of summation less costly?

I imagine finding the closed form of an algorithm should yield fewer steps than the original. But in the case of a summation from 1 to n, I'm not sure if it actually does. Here's the original sum <...
214 views

### Shortest path between all pairs of vertices in cyclic undirected weighted sparse graph

Is there any efficient algorithm to find shortest distance between all pairs of vertices? The graph is: Cyclic Sparse (each vertex has either 2 or 3 edge) undirected(bidirectional) weighted non-...
629 views

### What is more effective, a do while or a while?

I mean, with the same code, if I modify a do while into a while in this way: do {$S;$} while ($B$) into a $S;$ while ($B$){$S;$} , there is any change in the code? B = condition S; = instructions
98 views

### How to compare the efficiency of two encoding schemes or hypothesis languages?

My question is pretty basic, I'm looking for a named method if you know one, but also proper terminology, further reading, and anything this reminds you of if you don't. (I'm new to this, don't have ...
257 views

### Bucket Priority Queues with large integers for $O(1)$ insert and extract~min?

I recently got into a discussion about Priority Queues when the requirements allow for "best effort" removal (i.e. the removed key may not always be THE very highest priority, but it is relatively ...
47 views

### find number in array divided into k parts

I was wondering what is the most efficient way to find the a number in an array with the following conditions: Array $A$ of size $n$ divided into even parts in the size of $k$ every element ...
68 views

### Christmas Light Route Efficiency

This is a real situation (I hope it's ok that I post this here. If not, please suggest a better home). I have little knowledge of algorithms, but I know I can use one to solve this problem. I'm ...
2k 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 ...
1k views

### stack vs queue efficiency

Is there any literature / research on the average size efficiency of stacks vs queues? I asked because I was recently working on a problem where, if using a queue, the size quickly blew up and the ...
152 views

### Optimal generalized bisection method

Suppose I'm looking for a some unknown number $x$ in the interval $[a,b]$ under the following assumptions: $x$ is unique. Given any $t \in [a,b]$ I can check, at some fixed computational cost, ...
108 views

https://en.wikipedia.org/wiki/B-tree#Initial_construction Currently I know of 2 ways for building a B-Tree : bulkloading and just inserting key after key. In the wiki example the keys are sorted, ...
34 views

### Efficiently find the next item in a sequence to exceed some bounds

I have a bounded sequence of integers, and for each element, I want to know if the sequence next goes some distance above that element, below that element, or neither. This is straightforward in ...
I am working on a problem in which I have to solve 0-1 linear programs, that is linear programs where some of the variables are binary, i.e. either 1 or 0. Lets say I have a fixed number of $n$ ...