Hot answers tagged

28 votes

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 ...
user avatar
  • 25.6k
25 votes

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 ...
user avatar
23 votes
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: ...
user avatar
  • 599
16 votes

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 ...
user avatar
  • 19.1k
14 votes

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, ...
user avatar
10 votes

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 ...
user avatar
  • 9,325
9 votes

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 ...
user avatar
7 votes
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 ...
user avatar
  • 1,319
6 votes

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 ...
user avatar
6 votes
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 ...
user avatar
  • 143k
6 votes
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....
user avatar
  • 7,203
6 votes

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 ...
user avatar
5 votes

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-...
user avatar
5 votes
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 ...
user avatar
  • 7,203
4 votes

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'...
user avatar
  • 6,940
4 votes
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).
user avatar
4 votes

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 ...
user avatar
  • 4,706
4 votes

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 ...
user avatar
  • 161
4 votes
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 ...
user avatar
  • 156
4 votes
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 ...
user avatar
  • 5,214
4 votes

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 ...
user avatar
  • 25.6k
4 votes
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 ...
user avatar
  • 34.9k
3 votes
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: $$ ...
user avatar
3 votes
Accepted

Control of the combinatorial aspects of a dynamic programming solution

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$ ...
user avatar
3 votes

How can I optimize 3 variables in order to maximize the end product?

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)...
user avatar
  • 143k
3 votes
Accepted

Why does parallelising slow down this simple problem against looping through all the data?

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 ...
user avatar
3 votes

Complexity of iterative exponentiation

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 ...
user avatar
  • 25.6k
3 votes

Space complexity for storing integers in Python

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 ...
user avatar
3 votes
Accepted

Repeated addition and comparisons of floating point numbers

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 ...
user avatar
  • 103
3 votes

Can a 600 MB text file with digits of the square root of 2 be compressed to 600 KB?

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 ...
user avatar
  • 1,336

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