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

288 questions
Filter by
Sorted by
Tagged with
1 vote
23 views

### Algorithm for creating an esports season schedule

I run an esports league for my Boys & Girls Club and others that want to participate. I'm trying to find a way to take information about when different teams are available to compete and use that ...
25 views

### What could cause a Windows 11 machine to have so much more elapsed time relative to a Windows 10 machine?

I have a Windows 10 desktop (6 years old - Dell Optiplex) and a new Windows 11 laptop (maybe last years model - Lenovo Thinkpad P16 Gen2). I am running scripts in R to compare their compute times. The ...
• 111
1 vote
24 views

### Stable Flow Problem with one sided preferences

I'm currently working on a problem to come up with ideas to solve a stable flow problem but unlike the traditional stable flow problem where every node has preferences on its incoming and outgoing ...
• 11
1 vote
53 views

### Understanding crossover points in efficiency between insertion and merge sorts

Self-taught programmer here. I'm reading CORS, and right at the beginning, question 1.2-2, there asks a question: For inputs of size $n$, insertion sort runs in $8n^2$ steps, which merge sort runs in ...
121 views

### The awkward status of Mersenne Twister

Random number generators generally fit into 3 categories IMO: ad-hoc designs serving as stub to be replaced by something else if this ever happens, considerate designs aiming at achieving statistical ...
• 352
1 vote
46 views

### Efficient ways to sort pairwise distances for set of points in Euclidean space?

Consider a Euclidean space $\mathbb{R}^d$. Consider $X \subset \mathbb{R}^d$ where $X$ is a finite set with $|X|=n$. Consider the set of line segments $\{xy | x,y \in X\}$ . I have a process $Z$ that ...
• 13
93 views

### Algorithms for sorting under some restrictions

I was recently sorting a large list of names - I just ended up sorting it in Python, but it inspired in me the following question. If we're given a list $L$ of $n$ numbers, but can only see $k$ ...
54 views

### Telling unique values in a short array

I have thousands of short arrays (length less than 9) holding integers. These numbers can be identical with high probability (in many arrays there are two triples of equal numbers). I need to remove ...
33 views

### What the algorith should return and how to implement

I was studying algorithms, and that problem below came up. Write an efficient algorith that calculates the biggest single positive forward change in value given the values. There is a second image ...
1 vote
129 views

### Why use Welford's Method over a more naive approach?

I came across this pair of blog posts explaining the problem with calculating variance on floating point data: https://jvns.ca/blog/2023/01/13/examples-of-floating-point-problems/#example-3-a-variance-...
• 111
24 views

### Shortcut for multiple highly-redundant dot-products?

In statistical computing, we often have linear models that involve computing multiple vector dot products, but there's a high amount of redundancy in the operations when you break them down. As an ...
271 views

### Finding number of combinations of numbers from multiple arrays that add up to a given value

Let $A$ be an array of $n$ integer arrays with unknown lengths and $s \in \mathbb{Z}$ a given number. I want to find the number of combinations of numbers from each array, such that their sum ...
• 101
89 views

### Efficiently sorting a list of integers depending on the index of said integers in a second list

Introduction Hi everyone, I am currently pondering how to efficiently design an algorithm for a sorting problem and hope that someone here may help me out a bit. The problem I have two lists of ...
1 vote
53 views

### Are there adaptive algorithms/data structures for sparse and non sparse vectors?

A sparse 1D array of integers is commonly encoded as pairs of [index, value], which consumes 2 memory spots per value. A dense 1D array is commonly encoded as a linear array of values [value1, value2, ...
• 131
1 vote
110 views

### $O(n \log n)$ Algorithm for first Train Problem

On $n$ parallel rails there are $n$ trains with constant speeds $v_1, ..., v_n$. At time $0$ the trains are at positions $k_1, ..., k_n$. Find an $O(n \log n)$ algorithm that determines which trains ...
• 11
1 vote
76 views

### There is a problem-name and/or algorithm for calculating functions which are constant on different intervals?

I frequently have to calculate this kind of function Those functions have constant values on arbitrary (predefined) intervals I wonder if there is an algorithm for fast calculation of it, so I can ...
• 131
118 views

### What is the most computationally efficient Turing complete system?

I'm making a program that involves making models of and working with arbitrary systems (or programs). What is the most computationally efficient Turing complete system to model these in? By "...
65 views

### How much faster would a semantic segmentation model be with just 2 classes compared to 100 classes?

Let's say I have a semantic segmentation model that distinguishes between 100 classes of objects, and the speed of running the model is 1 image per second. Now let's say I take the same model ...
• 101
557 views

### Retrieving the cheapest path of a graph with time-dependent edge weights

There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the weights of edges are time-dependent? I'm trying to find an efficient ...
• 31
38 views

### The interpretation of expected time bound for searches in a hash table

As CLRS book,page 260 stated, Thus, the total time required for a successful search is $\Theta{\left(2+\alpha/2-\alpha/2n\right)}=\Theta{(1+\alpha)}$ I wouldn't have any problem if the author says ...
• 103
1 vote
25 views

### Number of operands to take when evaluating postfix notation?

All sources I have seen list taking two operands from the stack once we encounter an operator. Why? What if not all of my operators are binary (taking two arguments)? What if I have custom unary and ...
177 views

### Merging Tuples of Intervals

Suppose I have a list of tuples. Each tuple contains 2 intervals. The intervals in each tuple have nothing to do with each other. I would like to find a smaller list of tupels that covers all elements ...
• 63
159 views

### How to design fast/efficient algorithms?

Let's say, if you could travel to the past, what would you teach your younger self? Which key points define efficient algorithms?
1 vote
275 views

### Fast computing of a matrix power for large integer values in C++

I'm working with squared matrices that can be quite large, for instance, a M = 50 x 50 matrix. My objective is to compute the power of the squared matrix ...
• 113
1 vote
216 views

### Efficient way to find key points on spline to approximate it with line strip

Given a spline, what is an efficient way to find (approximately) the least amount (and position) of key-points to approximate the spline with a line strip, so that the largest distance between the ...
• 121
78 views

### How can we solve halting problem efficiently?

I was doing exercises regarding the halting problem and there is this question where I am stuck Ques: it goes like suppose if you can decide the halting problem with a query "Is <tm,s> ...
• 11
37 views

### Efficient method for finding 1's in binary representations

Say I have a binary number of N bits, and I need to find every combination that have M 1's. For example, if N = 3 and M = 1, then 100, 010, 001 are the allowed combinations. I have read that a more ...
1 vote
38 views

### Which of the query approaches are more efficient?

There are two relations, registered(participant,topic) and fee(participant,amount). The primary key for registered is (participant, topic) and the primary key for fee is participant. The premise is ...
36 views

### About the connection of pipelined execution and latency

Let's consider we want to calculate a[i]=a[i]*c for a vector the size of N=12 on some random processor. We do assume that ...
• 161
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: ...
• 123
1 vote
75 views

### Can we make at most 3 comparisons in the closest points algorithm instead of 7?

Let's say I am using the divide and conquer algorithm outlined here, but I only want to return the minimum distance. I understand why that algorithm puts an upper-bound at 7 but I think that can be ...
• 11
66 views

### Efficient triangular decomposition of an integer

Euclidean division is an iterative process that has been made super-efficient at the CPU level, right? Its specification is that if I do (q, r) = f(n, d), I get ...
• 195
1 vote
51 views

• 153
42 views

• 153
### Heaps and Heapsort - Find the 7'th biggest value in a min heap by $O(1)$
I have a min heap. I need to find the 7'th biggest value in the heap with $O(1)$. I need to build the algorithm. I dont realy have an idea how to get to this efficiency. Help? Thanks.