# Tag Info

### Time complexity of min() and max() on a list of constant size?

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

### Checking equality of integers: O(1) in C but O(log n) in Python 3?

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

### Does an algorithm's space complexity include input?

It depends on the chosen convention. I often prefer the convention that considers that the input is not part of the space complexity, for different reasons: the space complexity of a function answer ...
Accepted

### Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks?

Wikipedia has an extensive list of languages that use the off-side rule1: ABC Boo BuddyScript Cobra CoffeeScript Converge Curry Elixir (, do: ...

### Checking equality of integers: O(1) in C but O(log n) in Python 3?

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

### Time complexity of min() and max() on a list of constant size?

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

### Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks?

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

### Checking equality of integers: O(1) in C but O(log n) in Python 3?

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

### Space complexity for storing integers in Python

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

### Checking equality of integers: O(1) in C but O(log n) in Python 3?

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

### What are the fundamentals of calculating space complexity in loops?

I can't answer that question reliably, because it depends on the behavior of the memory allocator in Python, and I don't think we're provided any guarantees about that. The memory allocator might ...
Accepted

### Using pre-,post-, and in-order indexes to find information about a Binary Search Tree

Long story short: it is possible in constant time if the tree is a full binary tree. If not, there are some cases where there is not enough information to find the size of the subtree in constant time....

### Number of Inversions found in Selection sort vs Exchange sort

Here's another perspective. Less mathematical, but I think also insightful. Using a fabulous sort visualizer (taken from this), here's random data and how the data looks midway through sorting with ...

### Does an algorithm's space complexity include input?

Auxiliary Space: The extra space that is taken by an algorithm temporarily to finish its work Space Complexity: Space complexity is the total space taken by the algorithm with respect to the input ...

### Time complexity of min() and max() on a list of constant size?

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

### Why does Python allow stand-alone expressions?

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

### Doubt about computing running time / time complexity of a function in Python

You could say that this function has a time complexity of $\mathcal{O}(h)$, where $h$ is the height of the BST. You could be more precise and say that it is a $\Theta(h)$ in the worst case. This means ...

### Does this sorting algorithm already exist? And if so, what is its name?

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

### Why is this n^2 growth?

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

### Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks?

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

### How to wiggle sort an array in linear time complexity?

Some characterizations of wiggle-sort Skip this section if you would like to see the algorithms right away.$\def\A{\mathcal A}$ $\def\S{\mathcal S}$ Given an array $\A=(\A_0,\A_1, \cdots, \A_{n-1})$ ...

### Time complexity of min() and max() on a list of constant size?

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

### Warnsdorff's rule: more errors with odd sized boards

For odd-sized boards, a knight's tour must start and end on the same color as the corner squares of the board. It follows that for about half (50%) of starting squares, there is no possible knight's ...

### Doubt about computing running time / time complexity of a function in Python

While Nathaniel's answer is obviously right, there is something else to consider: Do the operations that you perform change the shape of your tree? I binary tree with 1000 nodes could have a height of ...
Accepted

### Number of Inversions found in Selection sort vs Exchange sort

Interesting question! Indeed, the expected numbers are quadratic and linearithmic respectively. Assumptions For ease of analysis, assume the numbers in the given array are distinct. This assumption ...
Accepted

### Compute hash value according to multiplication method

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