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.
285
questions
1
vote
1
answer
33
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 ...
- 113
2
votes
2
answers
87
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 ...
- 192
1
vote
1
answer
39
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
2
votes
1
answer
82
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$ ...
- 121
0
votes
1
answer
51
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 ...
user16034
0
votes
0
answers
30
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
1
vote
2
answers
73
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
0
votes
0
answers
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 ...
- 101
0
votes
1
answer
126
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
-1
votes
1
answer
61
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
1
answer
50
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
1
answer
86
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
2
answers
75
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
0
votes
0
answers
112
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 "...
0
votes
1
answer
47
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
3
votes
1
answer
396
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
0
votes
1
answer
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
1
answer
24
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 ...
3
votes
1
answer
171
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
-3
votes
1
answer
147
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
2
answers
248
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
2
answers
162
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
0
votes
1
answer
75
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
0
votes
0
answers
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
1
vote
0
answers
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 ...
0
votes
1
answer
34
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
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:
...
- 123
1
vote
0
answers
73
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
0
votes
0
answers
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
2
answers
49
views
Floating-point oblivious way to compute multiset numbers
I have to compute $R = \left(\!\!{n + 1\choose k}\!\!\right)$, which happens to be:
$$
R = \left(\!\!{n+1\choose k }\!\!\right) = \binom{n+k}{k} = \frac{(n + k)!}{n!k!} = \frac{(n+1)(n+2)\cdots(n+k)}{...
- 457
0
votes
1
answer
415
views
Making an algorithm that picks a unique random number in fixed set more efficient
I have been working on a project that simulates an online bank. At this point, I'm implementing the code used to create user accounts. Each account will have a sortcode and account number, I have ...
1
vote
0
answers
163
views
Convex hull on set of squares
Imagine a set of two to six squares within 3D-space. The goal is to generate a convex hull around these squares as efficiently as possible.
The following constraints are known:
Each of the two to six ...
- 111
2
votes
1
answer
397
views
Overhead cost of spawning child processes
I am curious as to the overhead cost of spawning child processes using fork in a Linux environment. Suppose I have a C program such as
...
- 115
1
vote
3
answers
162
views
Faster computation of $ke^{-(x - h)^2}$
The question is quite simple; almost every computer language today provides the $\exp(x)$ function in their standard library to compute expressions like $ke^{-(x - h)^2}.$ However, I would like to ...
-1
votes
1
answer
281
views
Finding most efficient sorting algorithm
Arr is an array that contains $ n$ numbers.
Suggest the most efficient algorithm for each case and analyze the runtime.
Explain why the algorithm you chose is the best one.
Arr contains exactly $\...
- 167
0
votes
3
answers
614
views
Big O Proof , f(n) = 2n + 1 and I have to prove f(n) is O n^2
If I have $f(n) = 2n + 1$ and I have to prove $f(n) \in O(n^2)$, by proving there exists positive constants $c$ and $n_0$ such that $f(n)<cn^2, \forall n\ge n_0$, can I do this all in one step by ...
0
votes
2
answers
194
views
How to prove Big-O when $f(n)$ is defined sectionwise
I'm given a function which is defined based on a condition, for example
$$
f(n)
= \begin{cases}
4n+1, \ \text{n is even}\\
3n^2+2, \ \text{n is odd}
\end{cases}.
$$
I have to prove or ...
-2
votes
2
answers
38
views
0
votes
1
answer
79
views
Efficient algorithm to compare arrays problem
I was submitted an interesting problem, but I wasn't able to find a solution.
Define a function p(x, y) that takes int x and y, with ...
anon
1
vote
2
answers
111
views
Understanding recursion tree for withdrawal formula
$$
T(n) = T(n-a) + T(a) + cn
$$
Now the solution says that the height of the tree $(h)$ is:
$$
h = \left \lfloor n/a \right \rfloor
$$
And I don't understand why. Maybe I didn't understand the ...
- 153
0
votes
1
answer
30
views
Why substituting the search part in INSERTION SORT doesnt yield a running time of $\Theta(nlgn)$
$$
\Theta - Tight \ asymptotic \ bound
$$
If we change lines $5-7$ in Insertion sort
With BINARY-SEARCH(A,p,r,v)
Why don't we get a running time of $\Theta(n\lg n)$ as we go through the array $\...
- 153
1
vote
2
answers
270
views
What's the most time efficient way to find the number of nodes reachable from each root and no other root?
Suppose there are n nodes.
These nodes are connected by m unique directed edges. Sets of these edges may form cycles.
Each node ...
- 15
0
votes
0
answers
22
views
Parent Node in BST
Is it a good idea to store a pointer to the parent node in a binary search rather than to find the parent node several times?
...
0
votes
3
answers
64
views
Comparing the efficiecy of 2 run times
I have a heap with $n$ elements.
$k$ represent a number that is the height of one of the elements in the tree.
I need to compare two run times and prove what i claim.
The 2 run times are:
$$
(1)O(...
- 153
0
votes
2
answers
41
views
Findind The n/lgn intermidiate values in an unsorted array with asymptotic run time of $\Theta(n)$ SELECT algorithm
Let $A[1..n]$ be an unsorted array, we want to find the $n/lgn$ intermidiate numbers in the array.
Namely the $(n/2)+1$ biggest number and the $(n/2) + 2$ biggest number and so on... until the $(n/2)...
- 153
-1
votes
1
answer
188
views
reordering a max heap that the values of one of her subtrees has been changed
Let $H$ be a max binary heap with $n$ elements (vertexes).
Pick a vertex $z$ in the heap with height of $k$ ($0<k<\lg n$)
To every element in the sub heap of $z$ we add the constant value $c &...
- 153
0
votes
2
answers
171
views
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.
- 153
0
votes
0
answers
24
views
What's the best bucket fill algorithm in terms of efficiency? [duplicate]
I am looking for an algorithm that fills a given region of connected particular nodes in minimum time. I have tried using flood flow algorithm but it's too slow and inefficient for large array, it ...
- 111
3
votes
1
answer
174
views
Dynamic Program to solve an NP-complete partitioning problem
I have this problem for which I am struggling to find an efficient dynamic programming algorithm. Would be thankful for some help!!
Let $A = \{ a_1, a_2, ..., a_n \}$ be a set where $a_i \in \mathbb{...
- 33
1
vote
1
answer
493
views
For $T(n) = 16T(n/4) + n^2\lg^3n$ prove: $T(n) = \Theta(n^2\lg^3n)$
Define:
$
\lg x = \log_2x
$.
Let
$
f(n), g(n)
$
be some non-negative functions.
Define
$
f(n) = \Theta (g(n))
$
if
$$
\exists c_1,c_2 \in R\colon 0 < c_1g(n) \leq f(n) \leq c_2g(n)
$$
I want ...
- 153