# Tag Info

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

24

That depends what exactly you mean by "constant sized". The time to find the minimum of a list with 917,340 elements is $O(1)$ with a very large constant factor. The time to find the minimum of various lists of different constant sizes is $O(n)$ and likely $\Theta(n)$ where $n$ is the size of each list. Finding the minimum of a list of 917,340 ...

23

Wikipedia has an extensive list of languages that use the off-side rule1: ABC Boo BuddyScript Cobra CoffeeScript Converge Curry Elixir (, do: blocks) Elm F# (if #light "off" is not specified) Genie Haskell (only for where, let, do, or case ... of clauses when braces are omitted) Inform 7 ISWIM, the abstract language that ...

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

13

I found this quote from the Wikipedia article on time complexity helpful: The time complexity is generally expressed as a function of the size of the input. So if the size of the input doesn't vary, for example if every list is of 256 integers, the time complexity will also not vary and the time complexity is therefore O(1). This would be true of any ...

10

There are: Elm, Haskell, its predecessor Miranda and its predecessor ISWIM, YAML where spaces are crucial for syntax and tabs are forbidden, OCCAM, Coffee script and Cokescript both are language to language compilers with JavaScript as target and esoteric Whitespaces. There is also Agda - interactive theorem prover, which is probably not what you had in ...

9

Is this correct? I haven't seen anyone else claim that Python compares ints in log time. No (and a little yes). Consider the following thought-provoking (but not really true) claim: A computer can only have a finite amount of memory (bounded by the number of atoms in the universe), so the Python version is also $O(1)$. The problem is that we are trying to ...

6

It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the size of input in bits. In this assumption, the sum of the input can be represented with 1 word, so the space complexity is $O(1)$ words. Measured in bits, the ...

6

Although this may seem like a trivial point, your first sentence is incorrect. The functions are not equivalent. To make them equivalent, the C function should use GMP (or similar) to implement arbitary-precision arithmetic. Now, the reason this observation is not trivial, is that the extent to which it's reasonable to say that the two are equivalent, is ...

5

Sure, you could call it O(1) if you want. So what if you choose to describe it that way? It's still going to iterate over the whole list, so describing it one way or the other doesn't change the real-world Python run time. It's still something you want to avoid doing repeatedly for the same list, especially if the list isn't tiny. (Especially in a loop ...

4

Unfortunately, this has no name—because it doesn't work. Pontus provided a good test case. lst = [2, 1, 3, 4, 5] sort_algo(lst) print(lst) [2, 1, 3, 4, 5] It's been mathematically proven that comparison-based sorting algorithms (that is, sorting algorithms based on comparing elements against each other, rather than exploiting certain clever tricks) can ...

4

Because $n + (n-1) + (n-2) + \cdots + 2 + 1 = \frac{n(n+1)}{2} \in \mathcal{O}(n^2)$. Note that $n^2$ is polynomial, not exponential (that would be $2^n$ for example).

4

Make fits your description, even though it probably isn't quite what you have in mind, with its limited syntax and power. It infamously indicates its code blocks (recipes) with a particular form of whitespace: one tab character. Alternative ways are available (e.g. GNU Make supports using an alternative character), but rarely used in practice. Another ...

4

Yes In general, if the time complexity of an algorithm is O(f(X)) where X is a characteristic of the input (such as list size), then if that characteristic is bounded by a constant C, the time complexity will be O(f(C)) = O(1). This is especially useful with certain algorithms that have time complexities that look like e.g. O(N ^ K). This is superexponential,...

4

The python creators decided that any expression is valid as a statement. While not all expressions are useful as statements, it would make the language more complex to have to remember which expressions may be statements and which can not. A second reason is that many expressions that may seem "safe" can still have side effects, making it useful to ...

3

You haven't extracted the 14 most significant bits. First, you have to write $r$ as a $w$-bit number: $$00000001000011001100000001000000$$ Now you extract the 14 most significant bits: $$00000001000011$$ Converting to decimal, this is 67.

3

There is absolutely no problem adapting dynamic programming to count solutions without regard to order (i.e., when order doesn't matter). Let $D(S,m,n)$ be the number of ways to obtain a change of $n$ using the first $m$ coins of $S = S_1,\ldots,S_M$. We have $D(S,m,0) = 1$, $D(S,m,n) = 0$ when $n < 0$, and otherwise  D(S,m,n) = \sum_{i=1}^m D(S,i,n-S_i)...

3

This area is known as black-box optimization: you have a function $f(x,y,z)$ where you have the ability to evaluate $f$ on an input of your choice, and you want to find $x,y,z$ that maximizes $f(x,y,z)$. (Here $x$ is the decision threshold, $y$ is the maximum % gain per trade, and $z$ is the stop loss, and $f(x,y,z)$ is the amount of ending money at the end ...

3

Parallelism has costs. The processes have to be scheduled, communicate with each other, manage resources, etc. In return you can do multiple things at the same time. When you have a lot of slow tasks that can be done independently, parallel processing will speed things up a lot. But when you try to parallelize an easy task it might take longer to handle ...

3

You are unsure how to answer the question. When you are unsure: I method that does usually not work is trying to think about the problem very hard and waiting for inspiration. It doesn't come. A method that works quite well is using pen and paper and trying it out. And you'll find that f (2, 64) calls f (64, 1) which doesn't make any further calls. Now ...

3

Resource usage always depends on your model of computation. If you're in a situation where integers can grow arbitrarily large then, yes, you need to take that into account. One way of doing this is by assuming that integer variables take an amount of space that depends on the value stored. Another way is to use something like the word RAM model, which more ...

3

The reason you are seeing these results are not due to the memory limits of your computer, but rather of the limits of the encoding of "floating point" numbers. Python uses 64 bit floats (aka double precision floating point numbers), which are well described on wikipedia: https://en.wikipedia.org/wiki/Double-precision_floating-point_format In short, there ...

3

Clearly that's a way too good compression rate. $\sqrt{2}$ is not a rational number, so the decimal expansion will not start repeating. So there has to be something really fishy going on. I run your script, and looked at the resulting file. On my machine, the file square_root_of_2_with_536870912_bits.txt contains 161.614.250 digits, and the last 161.597.755 ...

3

In order to discuss the expected time complexity of an operation, you have to specify a distribution on the inputs, and also explain what you mean by $n$. One has to be careful, however. For example, consider the suggestion in the comments, to consider some kind of distribution over words of length at most 20. In this case, string comparison is clearly $O(1)$...

3

In the copy that I have of IEEE 754 (2008) it says 7.3 Division by zero 7.3.0 The divideByZero exception shall be signaled if and only if an exact infinite result is defined for an operation on finite operands. The default result of divideByZero shall be an ∞ correctly signed according to the operation: ― For division, when the divisor is zero and the ...

3

The running time is polynomial with memoization. If the original input string has $n$ characters, then there are only $O(n)$ possible suffixes of the original string, the function is only called on a suffix of the original string, and (ignoring recursive calls) the time to execute the function is polynomial; so the total running time with memoization is ...

3

The Bentley-Ottmann algorithm can be used to find all intersections between edges, and then you can add a node at each such intersection.

2

Your problem is a slightly more general version of computing the vertex-connectivity of a graph. If all weights are equal, then it is equivalent to the vertex-connectivity problem. The problem can be solved in polynomial time with network flow, yes; but you'll need to invoke a network flow subroutine several times; just one invocation won't be enough. ...

2

So you have the right logic, if you have a loop of $O(n)$ iterations, the complexity of the entire loop will be $O(n*\text{complexity of loop operations})$. In this case, you again are correct that your loop's complexity is $O(n)$ for each iteration. Your last bullet point shows that you understand this as well, as the total loop complexity is then $O(n^2)$...

2

Let's call your proposal X, instead: X = lambda f : (lambda x : f( lambda z: x(x) (z) )) (lambda x : f(x(x))) For convenience, we can rewrite it as M = (lambda x : f(x(x))) # depends on f X = lambda f : (lambda x : f( lambda z: x(x) (z) )) M Now, when we invoke X(f), we get X(f) = (lambda x : f( lambda z: x(x) (z) )) M = f( lambda z: M(M) (z) ) ...

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