281

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


99

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


91

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


51

The best algorithm that is known is to express the factorial as a product of prime powers. One can quickly determine the primes as well as the right power for each prime using a sieve approach. Computing each power can be done efficiently using repeated squaring, and then the factors are multiplied together. This was described by Peter B. Borwein, On the ...


37

All complexities you provided are true, however they are given in Big O notation, so all additive values and constants are omitted. To answer your question we need to focus on a detailed analysis of those two algorithms. This analysis can be done by hand, or found in many books. I'll use results from Knuth's Art of Computer Programming. Average number of ...


36

On the contrary. At the same time that hardware is getting cheaper, several other developments take place. First, the amount of data to be processed is growing exponentially. This has led to the study of quasilinear time algorithms, and the area of big data. Think for example about search engines - they have to handle large volumes of queries, process large ...


31

I really like the example from Introduction to Algorithms book, which illustrates significance of algorithm efficiency: Let's compare two sorting algorithms: insertion sort and merge sort. Their complexity is $O(n^2) = c_1n^2$ and $O(n\log n) = c_2n \lg n$ respectively. Typically merge sort has a bigger constant factor, so let's assume $c_1 < c_2$. To ...


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


21

Keep in mind that the factorial function grows so fast that you'll need arbitrary-sized integers to get any benefit of more efficient techniques than the naive approach. The factorial of 21 is already too big to fit in a 64-bit unsigned long long int. As far as I know, there is no algorithm to compute $n!$ (factorial of $n$) which is faster than doing the ...


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

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

Other answers have addressed this from a more theoretical perspective. Here is a more practical approach. For "typical" NP-complete decision problems ("does there exist a thingy that satisfies all these constraints?"), this is what I would always try first: Write a simple program that encodes your problem instance as a SAT instance. Then take a good SAT ...


13

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


12

The asymptotic cost, or $\mathcal O$-notation, describes the limiting behaviour of a function as its argument tends to infinity, i.e. its growth rate. The function itself, e.g. the number of comparisons and/or swaps, may be different for two algorithms with the same asymptotic cost, provided they grow with the same rate. More specifically, Bubble sort ...


12

The knowledge of algorithms is much more than how to write fast algorithms. It also gives you problem solving methods (e.g. divide and conquer, dynamic programming, greedy, reduction, linear programming, etc) that you can then apply when approaching a new and challenging problem. Having a suitable approach usually leads to codes which are simpler and much ...


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


12

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


11

Since the factorial function grows so fast, your computer can only store $n!$ for relatively small $n$. For example, a double can store values up to $171!$. So if you want a really fast algorithm for computing $n!$, just use a table of size $171$. The question becomes more interesting if you're interested in $\log(n!)$ or in the $\Gamma$ function (or in $\...


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


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