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.

learn more… | top users | synonyms

0
votes
1answer
21 views

Can any algorithm efficiently be implemented as a SIMT problem?

Many algorithms can be implemented more efficiently using SIMT instructions (e.g. CUDA) than using sequential instructions. Excluding overhead due to hardware limitations (specifically, memory copy ...
1
vote
1answer
44 views

What is more efficient: gcd(x,y) or brute force, when x and y are a very big numbers

I implemented the quadratic sieve algorithm as it's described in wiki. Most of the work of the algorithm is to determine if some big integer $Y$ belongs to the vector $b[b_1,b_2,b_3,\ldots]$. So far ...
5
votes
1answer
240 views

From Guido's essays, how does this function avoid quadratic behavior in a string concatenation algorithm?

I am reading one of Guido van Rossum's essays on optimization in Python. We are interested in converting a Python list of integers to their character equivalents. Here's the straightforward ...
1
vote
1answer
27 views

Efficient formulation for binary integer linear programming

Problem: There are two types of balls, big (B) and small (S), which need to packed into boxes. One box can contain either: nothing, or 1 S, or 1 B, or 2 S, or 2 B, or 1 B and 2 S We are given the ...
0
votes
1answer
19 views

In terms of the multiplicative constant, what comparison algorithm is fastest in average complexity? [closed]

It is well-known that there is an asymptotic lower bound of $nlogn$ for comparison sorting. However, I am wondering what is the fastest known algorithm for comparison sorting, in terms of the ...
3
votes
2answers
76 views

Average Cost Threshold Protocol with Minimum Thresholds: How to find the price?

The protocol is defined here, but I'll give a summary here. Okay, so a number of agents want a certain public good to be constructed (a public good is something like a book, a program, or a statue, ...
3
votes
1answer
36 views

Efficient algorithm to compute the minimum of multiple piecewise linear functions

Let $f_i(x)$ be a continuous, convex, piecewise-linear function for $i=1,\ldots,n$. Define $$g(x) = \min_{1\leq i\leq n} f_i(x).$$ Clearly, $g(x)$ is also a piecewise linear function. What would be ...
0
votes
4answers
75 views

Is it feasible to generate every possible RGB image?

This topic is normally brought up in computer science as a demonstration of how to calculate permutations but it stops there since we usually end up calculating that there are more images of a decent ...
1
vote
2answers
42 views

Does having one large L1 cache instead of L1 and L2 cache makes computation faster?

Does having one larger L1 cache instead of L1 and L2 cache makes computation faster? Also will this make the CPU more expensive to make?
1
vote
1answer
57 views

What is the fastest algorithm for finding shortest path in undirected edge-weighted graph?

I am looking for the most efficient algorithm for finding shortest path between two Vertices. The graph is: undirected edge-weighted Non-negative less then 300 nodes I understand that most of ...
9
votes
3answers
1k 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 ...
1
vote
1answer
38 views

Can computation models be categorized in terms of efficiency?

It is widely accepted that turing-complete systems are equivalent in terms of computability - i.e., whatever a turing-machine can do, can be emulated by automatas, the lambda calculus and other ...
1
vote
2answers
64 views

Hash table versus binary search lookup for unchanging data

Let's say I have some static, unchanging data (no adds, modifies or deletes) which is looked up by a string value, and that I'm looking to minimize size in memory while also trying to minimize lookup ...
0
votes
1answer
79 views

How to modify Floyd-Warshall algorithm with space $O(V^2)$ with tracking actual path?

The Naive way to reduce space complexity of Floyd-Warshall algorithm is consider only $d_{ij}^{(k)}$ and $d_{ij}^{(k-1)}$ in each time. But in this case, we can't track actual shortest path with ...
1
vote
1answer
31 views

How can I compare two different neural networks, from a theorical point of view?

Let's say I have a problem (i.e. Given f(x), find x) and two neural networks(i.e. feedforward and recurrent). I would like to know if one works better than the other one. I could run the twos on a ...
3
votes
1answer
52 views

Constant Shaving on known algorithms

Some problems such as sorting have famous complexity lower bounds (ex: $O(n \log (n))$ in this case) but I feel that doesn't totally remove the possibility of improving algorithms by shaving ...
4
votes
2answers
97 views

Practical exponential time algorithms for polynomial-time solvable problems

Inspired by this quote attributed to Alan Perlis: For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run. How I interpret this statement is that ...
2
votes
1answer
71 views

Quick Sort: Randomized Pivot vs Median of 3/'Ninther' Pivot vs Uniform Shuffle of Input

Is the jury still out on this or do we now know which of the above mentioned ways of randomizing Quick Sort is the most optimum as far as average case running time (averaged over all possible input ...
2
votes
1answer
68 views

Does proving a problem is in P typically mean it will eventually be practically solvable?

I'm currently reading Introduction to the Theory of Computation by Michael Sipser and in his section on time complexity, he tries to justify why theoretical computer scientists divide problems into P ...
5
votes
1answer
61 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 ...
1
vote
1answer
92 views

How to improve the binomial algorithm?

Good evening! I tried to model the Binomial theorem, that allows to expand any power of x + y into a sum of the form: $$(x+y)^n = {n \choose 0}x^n y^0 + {n \choose 1}x^{n-1}y^1 + {n \choose ...
3
votes
1answer
84 views

Why are division/floating points inefficient in comparison to integer addition/multiplication/subtraction?

Why does Bresenham's line algorithm eliminate dy/dx division and the multiplication of that (potentially floating point) number?
1
vote
0answers
32 views

Efficiently comparing total values of two unsorted arrays [closed]

The general form of my question would be, what is the most efficient way to compare the total values of two different arrays to see which one is greater? Would be as simple as prefix sum ($O(n)$) for ...
1
vote
0answers
42 views

Efficient method to sort very large set of integer vectors by all coordinates simultaneously

I have a set $E$ which is the set of all possible $d$-tuples ($d$-dimensional vectors) of integers between $1$ and $n$. Typically $d=3$ and $n\approx1000$, but for the sake of making a small example, ...
5
votes
2answers
87 views

Finding the k-th smallest rational number efficiently

Consider the following set: $S := \left\{\frac{a}{b} \colon a \in \{1,\ldots,A\}, b \in \{1,\ldots,B\} \right\}$ $S$ is the set of all rational numbers that can be represented by two integers $a$ ...
0
votes
0answers
11 views

how to calculate the average case efficiency of the improved bubble sort? [duplicate]

I already know that the average case efficiency for this algorithm is: $\Theta(n^2)$. But I want to know how to obtain this result. This is the algorithm that I have: ...
108
votes
10answers
38k 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, ...
2
votes
1answer
79 views

Best data structure for high dimensional nearest neighbor search

I'm actually working on high dimensional data (~50.000-100.000 features) and nearest neighbors search must be performed on it. I know that KD-Trees has poor performance as dimensions grows, and also ...
0
votes
0answers
60 views

Aliens to the Moon

$N$ Aliens want to reach their Moon ($D$ meters away), but they can only put on each other, making a vertical chain. Every $Alien(i)$ has an height $X(i)$ and a lenght of their arms $Y(i)$. ...
5
votes
2answers
115 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 ...
0
votes
1answer
60 views

Why don't 2 GPUs double the graphics performance of a computer compared to a single GPU?

Obviously, if you have 2 GPUs, it is double the hardware, and thus it should be double the power of a single GPU (assuming all GPUs are the same, of course). So why is this not the case? I searched ...
0
votes
2answers
233 views

Data structure with constant time operations

I need to use a data structure, implementable in C++, that can do basic operations, such as lookup, insertion and deletion, in constant time. I, however, also need to be able to find the maximum value ...
4
votes
2answers
131 views

Encircling randomly distributed points

I'm trying to solve an interesting problem. Imagine a square surface, onto which we spray randomly $p$ points. We also (randomly) place $c$ circle centres. I'm trying to find an algorithm that will ...
0
votes
1answer
90 views

Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true?

I've read and been told way too many times that functional algorithms and data structures have an obligatory O(log(N)) slowdown in respect to their procedural ...
1
vote
1answer
137 views

Efficient algorithm for conversion of hexadecimal fraction to decimal fraction

Let's say I have some very long hex fraction like this: 0.3F30A21306AEFCBADE3230A593EFAEB395A39E What are some algorithms with an acceptable complexity to ...
5
votes
3answers
339 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, ...
5
votes
3answers
267 views

Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?

I'm currently reading the elements of programming book and have come across a section I don't quite understand A computational basis for a type is a finite set of procedures that enable the ...
0
votes
1answer
196 views

Why is O(n log n) the best runtime there is?

I am taking a course on Coursera about algorithm design. The course said that a time of $O(n \log n)$ is considered to be good. However, there are faster runtimes such as (from now on just assume it ...
1
vote
1answer
63 views

How can a set offer better search performance than an array

While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer ...
6
votes
3answers
178 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 ...
3
votes
0answers
74 views

Find a sorting procedure for seven elements that minimises the average number of comparisons performed

In The Art Of Computer Programming, Volume 3, Chapter 5.3.1, Problem 26, Knuth asks one to construct a sorting method that achieves the minimum number of average comparisons for n=7. This means that ...
5
votes
1answer
115 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 ...
1
vote
1answer
43 views

Determining most efficient algorithm for a problem [duplicate]

This is a very straightforward question, and I apologize if it is a repeat. All I want to know is if there is any general method for determining how efficient the most efficient algorithm for some ...
1
vote
1answer
72 views

Better algorithm for determining if a vertex is on any cycle in a graph

The problem I'm facing is the following: Given a simple undirected graph $G=(V,E)$ and a vertex $u \in V$, answer if $u$ is part of any cycle of $G$. The algorithm I can think of is to remove an ...
4
votes
2answers
64 views

Limiting memory usage while keeping score

For an assignment we are asked the following(simplified) : A function F(a) has a non-negative integer as a result. This result is reused in the function itself. Like this, and where the first a is ...
0
votes
1answer
91 views

What sorting algorithm should be used for this array?

I am given an array {1, 2, 3, 5, 4, 6} and I am asked What sorting algorithm might you want to use to sort the given list, and why? Initially I think using ...
4
votes
1answer
122 views

Making a branch-and-bound algorithm more efficient for a large input

I am trying to implement the branch and bound algorithm to solve the knapsack problem (in the Coursera discrete optimisation course). I tried implementing dynamic programming first, and that worked ...
1
vote
1answer
30 views

Efficiently compute a complete set of representatives of cyclotomic cosets of $2$ modulo $2^n-1$

Let $n > 1$. For an integer $k$ with $0 \leq k \leq 2^n-2$ the cyclotomic class $C_k$ of $2$ modulo $2^n-1$ is the set given by $$C_k = \{k, k\cdot 2, k \cdot 2^2 , \ldots, k\cdot 2^{n-1} \pmod ...
1
vote
0answers
49 views

Median-of-medians for sorting finger trees incrementally

Haskell's Data.Sequence uses Hinze-Paterson 2-3 finger trees to represent finite sequences. The types are defined below for concreteness. Currently, the library ...
5
votes
5answers
2k views

What is the best solution to find whether the sum of an array is even or odd

I was asked this question in an interview. I was not able to find a better solution than $O(n)$ which is just going over the array and finding the sum. Can it be done any better? I am not really ...