146

Translating Code to Mathematics Given a (more or less) formal operational semantics you can translate an algorithm's (pseudo-)code quite literally into a mathematical expression that gives you the result, provided you can manipulate the expression into a useful form. This works well for additive cost measures such as number of comparisons, swaps, statements,...


87

When you change the base of logarithm the resulting expression differs only by a constant factor which, by definition of Big-O notation, implies that both functions belong to the same class with respect to their asymptotic behavior. For example $$\log_{10}n = \frac{\log_{2}n}{\log_{2}10} = C \log_{2}{n}$$ where $C = \frac{1}{\log_{2}10}$. So $\log_{10}n$ ...


79

If you apply binary search, you have $$\log_2(n)+O(1)$$ many comparisons. If you apply ternary search, you have $$ 2 \cdot \log_3(n) + O(1)$$ many comparisons, as in each step, you need to perform 2 comparisons to cut the search space into three parts. Now if you do the math, you can observe that: $$ 2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)}...


61

This algorithm can be re-written like this Scan A until you find an inversion. If you find one, swap and start over. If there is none, terminate. Now there can be at most $\binom{n}{2} \in \Theta(n^2)$ inversions and you need a linear-time scan to find each -- so the worst-case running time is $\Theta(n^3)$. A beautiful teaching example as it trips up the ...


43

Sure. Certainly. Here's how to reconcile your discomfort. When we analyze the running time of algorithms, we do it with respect to a particular model of computation. The model of computation specifies things like the time it takes to perform each basic operation (is an array lookup $O(\log n)$ time or $O(1)$ time?). The running time of the algorithm ...


37

An algorithm is polynomial (has polynomial running time) if for some $k,C>0$, its running time on inputs of size $n$ is at most $Cn^k$. Equivalently, an algorithm is polynomial if for some $k>0$, its running time on inputs of size $n$ is $O(n^k)$. This includes linear, quadratic, cubic and more. On the other hand, algorithms with exponential running ...


34

If you assume that the $\lambda$-calculus is a good model of functional programming languages, then one may think: the $\lambda$-calculus has a seemingly simple notion of time-complexity: just count the number of $\beta$-reduction steps $(\lambda x.M)N \rightarrow M[N/x]$. But is this a good complexity measure? To answer this question, we should clarify ...


32

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


31

Execution Counts of Statements There is another method, championed by Donald E. Knuth in his The Art of Computer Programming series. In contrast to translating the whole algorithm into one formula, it works independently from the code's semantics on the "putting things together" side and allows to go to a lower level only when necessary, starting from an "...


29

DCTLib is right, but forget the math for a second. By your logic then, n-ary should be the fastest. But if you think about it, n-ary is exactly equal to a regular iteration search (just iterating through the list 1 by 1, but in reverse order). First you select the last (or next to last) item in the list and compare that value to your comparison value. Then ...


29

This is Collatz conjecture - still open problem. Conjecture is about proof that this sequence stops for any input, since this is unresolved, we do not know how to solve this runtime recurrence relation, moreover it may not halt at all - so until proven, the running time is unknown and may be $\infty$.


25

Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit. Not quite. C ints are machine-word-sized and compared with a single machine instruction; Python ints are represented in base $2^{30}$ (see e.g. https://rushter.com/blog/python-integer-implementation/) and compared digit-by-digit in that base. So ...


23

Algorithm complexity is designed to be independent of lower level details. No, not really. We always count elementary operations in some machine model: Steps for Turing machines. Basic operations on RAMs. You were probably thinking of the whole $\Omega$/$\Theta$/$O$-business. While it's true that you can abstract away some implementation details with ...


21

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case. Quicksort usually has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array ...


18

There is a huge variety of feasible approaches. Which is best suited depends on what you are trying to show, how much detail you want or need. If the algorithm is a widely known one which you use as a subroutine, you often remain at a higher level. If the algorithm is the main object under investigation, you probably want to be more detailed. The same can ...


17

Here is an $O(n)$ algorithm solving the problem. Use the worst-case $O(n)$ selection algorithm to determine the $n-m+1$-th order statistics. Let $k$ be this number, which is the smallest of the $m$ largest numbers we are trying to determine. Now partition the array around the pivot $k$ using the QuickSort partition function. This step takes $O(n)$ too. ...


17

if there are any practical applications of this algorithm in the domain of computer science besides being a theoretical improvement The application of this algorithm is trivial - you use it whenever you want to compute a median of a set of data (array in other words). This data may come from different domains: astronomical observations, social science, ...


16

While the algorithm you mention appears in Knuth's TAOCP, it is certainly not due to Knuth, and is more widely known as the Schönhage–Strassen algorithm; Knuth even attributes this algorithm to them in the text. This algorithm indeed runs in linear time in the so-called RAM machine, in which variables are allowed to hold integers of size $O(\log n)$, where $...


16

It seems that the main sticking point of the question here is: Why express runtime in terms of the size of the input, rather than the numeric value that the input represents? And indeed in some cases it doesn't make much difference which way you choose to express it. For instance, we could say that the time to read all values in an $N\times N$ matrix is ...


16

Complexity is defined relative to a computation model. P and NP, for example, are defined in terms of Turing machines. For comparison, consider the word RAM model. In this model, memory is divided into words, words can be accessed in constant time, and the size of the problem can be represented using $O(1)$ words. So, for example, when analysing a comparison-...


15

The worst case complexity for quicksort is $\Theta(n^2)$. This is achieved by picking pivots that divide the set such that one group has only a single member. With a bad pivot picking algorithm, this can easily be achieved by picking one end of a sorted set. Your assumption is correct.


15

If you don't know anything about the contents of the matrix (such as some kind of monotonicity property), linear time is the best you can do for a one-off search with a deterministic algorithm by a simple adversary argument: if you don't look at everything, then you can't distinguish between the cases where the maximum component is/isn't one of the ones you ...


15

You translated the code correctly. There are many methods for solving recurrences. However, it is currently unknown if collatz even halts for all n; the claim that it does is known as Collatz conjecture. Therefore, no known method will work on this recurrence. I think $T(n)$ will be $\lg n$ if $n$ is even How so? I guess you are thinking of $n=2^k$, for ...


14

This is actually a deep issue that has some methodic and some pragmatic answers. I assume you want to know something about the algorithm(s) at hand. If you want to know which algorithm works better on a given machine on given inputs, go ahead and measure runtimes. If you want to compare the quality of a compiler for a given algorithm, go ahead and measure ...


14

Expanding on Reza's answer, every recurrence of the form $T(n) = T(n-1) + T(n-2)$, with arbitrary initial values, has a solution of the form $$ T(n) = A \left( \frac{1+\sqrt{5}}{2} \right)^n + B \left( \frac{1-\sqrt{5}}{2} \right)^n, $$ for some $A,B$. Note that $|(1-\sqrt{5})/2| < 1$, and so the second term tends to zero as $n \longrightarrow \infty$. ...


14

If the program runs forever, its running time is infinite. So, if it always enters an infinite loop, its running time is infinite. This is a degenerate case. Normally we focus only on algorithms that are certain to terminate (but see footnote). See also How to come up with the runtime of algorithms? and Is there a system behind the magic of algorithm ...


13

Try the following: The weight $w_i$ of an element $i$ in the heap $H$ is its depth in the corresponding binary tree. So the element in the root has weight zero, its two children have weight 1 and so on. The you define as potential function $$\Phi(H)=\sum_{i\in H}2 w_i.$$ Let us now analyze the heap operations. For insert you add a new element add depth $...


13

You ask, I have an $O(2^n)$ runtime, why do I not observe $2^n$ recursive calls for $n=15$? There are many things wrong in the implied conclusion. $O(\_)$ only gives you an upper bound. The true behaviour may be of much smaller growth. Asymptotics (like $O(\_))$ only give you only something in the limit, that is you can only expect the bound to hold ...


13

The time complexity function is \begin{cases} T(n)= O(1) \text{ for } n\le 1\\ T(n)=T(n/2) + O(1) \text{ for } n\text{ even}\\ T(n)=T(3n+1) + O(1)\text{ for } n\text{ odd}\\ \end{cases} which can be rewritten as the following if you are interested in asymptotic time complexity. \begin{cases} T(n)= 1 \text{ for } n\le 1\\ T(n)=T(n/2) + 1 \text{ for } n\...


13

Median filtering is common in reduction of certain types of noise in image processing. Especially salt and pepper noise. It works by picking out the median value in each color channel in each local neighbourhood of the image and replacing it with it. How large these neighbourhoods are can vary. Popular filter sizes (neighbourhoods) are for example 3x3 and ...


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