284

There is no necessary relation between the implementation of the compiler and the output of the compiler. You could write a compiler in a language like Python or Ruby, whose most common implementations are very slow, and that compiler could output highly optimized machine code capable of outperforming C. The compiler itself would take a long time to run, ...


100

How can a machine built by a man be stronger than a man? This is exactly the same question. The answer is that the output of the compiler depends on the algorithms implemented by that compiler, not on the langauge used to implement it. You could write a really slow, inefficient compiler that produces very efficient code. There's nothing special about a ...


94

I want to make one point against a common assumption which is, in my opinion, fallacious to the point of being harmful when choosing tools for a job. There is no such thing as a slow or fast language.¹ On our way to the CPU actually doing something, there are many steps². At least one programmer with certain skillsets. The (formal) language they program ...


31

I see four main ways to solve this problem, with different running times: $O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes linear time. You carry out $n$ deletions; therefore, this algorithm takes quadratic time. $O(n \: log \: n)$ solution: sort the arrays beforehand; then, perform a ...


29

The confusion arises from difference between the conceptual description of the algorithm, and its implementation. Logically merge sort is described as splitting up the array into smaller arrays, and then merging them back together. However, "splitting the array" doesn't imply "creating an entirely new array in memory", or anything like that - it could be ...


25

Quick answer: Never, for practical purposes. It is not currently of any practical use. First, let's separate out "practical" compositeness testing from primality proofs. The former is good enough for almost all purposes, though there are different levels of testing people feel is adequate. For numbers under 2^64, no more than 7 Miller-Rabin tests, or ...


23

There is one forgotten thing about optimisation here. There was longish debate about fortran outperforming C. Putting apart malformed debate: the same code was written in C and fortran (as testers thought) and performance was tested based on same data. The problem is, these languages differ, C allows pointers aliasing, while fortran does not. So the codes ...


19

The (asymptotically) most efficient deterministic primality testing algorithm is due to Lenstra and Pomerance, running in time $\tilde{O}(\log^6 n)$. If you believe the Extended Riemann Hypothesis, then Miller's algorithm runs in time $\tilde{O}(\log^4 n)$. There are many other deterministic primality testing algorithms, for example Miller's paper has an $\...


18

Yes, Grover's algorithm shows you can use a quantum algorithm to find an element in an unordered database of size $N$ with high probability by querying the database only $O(\sqrt{N})$ times. Any classical solution that succeeds with high probability requires $\Omega (N)$ queries to the database.


18

It's called "loop fusion". It's often more efficient, in the sense of doing more work per loop iteration and sometimes (as you say) other advantages. On the other hand, the fused loop in your example may also put more pressure on the CPU's cache prefetch system. So do test it before declaring it more efficient.


16

The $\Theta(n)$ difference-of-sums solution proposed by Tobi and Mario can in fact be generalized to any other data type for which we can define a (constant-time) binary operation $\oplus$ that is: total, such that for any values $a$ and $b$, $a \oplus b$ is defined and of the same type (or at least of some appropriate supertype of it, for which the ...


15

Here I assume $0\in \mathbb N$. If you disagree start with $105$. Let $S$ be the sequence of numbers of the form $3^i5^j7^k$. Our task is to generate these numbers in order. Apart from $1$ each number added is of the form $3\cdot x$, $5\cdot y$ or $7\cdot z$ where $x,y,z$ are previous numbers in the sequence. We can generate $S$ by shifting $x,y,z$ along ...


15

I'd post this as a comment on Tobi's answer, but I don't have the reputation yet. As an alternative to calculating the sum of each list (especially if they are large lists or contain very large numbers that might overflow your data type when summed) you can use xor instead. Just calculate the xor-sum (i.e. x[0]^x[1]^x[2]...x[n]) of each list and then xor ...


14

Because the actual running time (in seconds) of real code on a real computer depends on how fast that computer runs the instructions and how fast it retrieves the relevant data from memory, how well it caches it and so on. Insertion sort and quicksort use different instructions and hava different memory access patterns. So the running time of quicksort ...


14

Indeed there is a linear time algorithm for this. You only need to use some basic number theory concepts. Given two numbers $n_1$ and $n_2$, their sum is divisible to $K$, only if the sum of their remainder is divisible to $K$. In other words, $$K \mid ( n_1 + n_2 ) ~~~~ \Longleftrightarrow ~~~~ K \mid \left((n_1 ~mod ~K) + (n_2 ~mod ~K)\right).$$ The ...


14

Element = Sum(Array2) - Sum(Array1) I sincerely doubt this is the most optimum algorithm. But it's another way to solve the problem, and is the simplest way to solve it. Hope it helps. If the number of added elements is more than one, this won't work. My answer has the same run time complexity for best, worst, and average case, EDIT After some thinking, ...


13

The simplex method for linear programming has worst case exponential time complexity but is widely used in practice instead of the polynomial algorithms (which do exist).


12

By a simple "adversary argument", you have to check each element (in some way): Suppose you have missed some element $x$ and get an answer "The sum is even": the adversary can modify $x$ (if it's odd, make it even; if it's even, make it odd), which will change the correct result but not your computation. The adversary argument tells that in theory you have ...


12

The previous answers give pretty much the explanation, though mostly from a pragmatic angle, for as much as the question makes sense, as excellently explained by Raphael's answer. Adding to this answer, we should note that, nowadays, C compilers are written in C. Of course, as noted by Raphael their output and its performance may depend, among other things, ...


11

A basic data structure that allows insertion and deletion in time $\Theta(\log n)$ are balanced binary search trees. Their memory overhead is reasonable (in case of AVL trees, two pointers and three bits per entry) so millions of entries are no problem at all on modern machines. Note that in a search tree, finding the minimum (or maximum) is conceptually ...


11

In my other answer I suggest that conditional jumps might be the main impediment to efficiency. As a consequence, sorting networks come to mind: they are data agnostic, that is the same sequence of comparisons is executed no matter the input, with only the swaps being conditional. Of course, sorting may be too much work; we only need the biggest two ...


11

I guess what you mean is the bottom-up implementation. In the bottom up implementation you start from single cell elements an move upward by merging elements into larger sorted lists/arrays. Just reverse the arrows in your figure above starting from the middle array, i.e., one-element arrays. Also, you may want to optimize the merge sort by dividing arrays ...


10

There are certainly ways to show that certain algorithms must take a certain amount of time or certain data structures require a certain amount of space. One common way is to use information theory. An unsorted array is a permutation of the sorted array. There are $n!$ possible permutations. The job of sorting, in an information theoretic sense, is to ...


10

Since this question was reopened and made more explicit, I would like to convert my comment into an answer. Now the OP wants to understand why and when polynomial algorithms became of interest. I especially focus on the sub-question: When did people realize the role and importance of efficient versus non-efficient algorithms? Because algorithms, in ...


9

The main reason for choosing D* is that it is incremental. Basically, when your initial route gets blocked, an incremental search algorithm is able to take advantage of the previous calculations. Dijkstra doesn't do this; it needs to recompute everything from scratch. Such an incremental approach is often used in robotics, navigation, and planning. This is ...


9

Let's assume that adding two strings of lengths $a,b$ takes time $a+b$. Consider the following strategy to convert a list of $n$ characters into a list: Read the list in chunks of $k$, convert them to strings, and sum the chunks. Creating each chunk takes time $\Theta(1+2+\cdots+k) = \Theta(k^2)$, and we do this $n/k$ times, for a total of $\Theta(nk)$. ...


8

Joe's answer is extremely good, and gives you all the important keywords. You should be aware that succinct data structure research is still in an early stage, and many of the results are largely theoretical. Many of the proposed data structures are quite complex to implement, but most of the complexity is due to the fact that you need to maintain ...


8

It is impossible to build a data structure that supports insert, maximum, and delete all in constant time. Such a data structure is a priority queue, and a priority queue with all constant-time operations can do heapsort in linear time. Since there is a superlinear lower bound on sorting, this is impossible. One of insert, maximum, or delete must be ...


8

The number of such images is exponentially large in the dimensions of the image (even after taking into account symmetries), and grows enormous rapidly. For all but very small images, no, it's not feasible to enumerate all such images within the lifetime of the solar system. (There's something wrong with your reasoning if you've concluded it's reasonably ...


Only top voted, non community-wiki answers of a minimum length are eligible