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 ...
gnasher729's user avatar
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 ...
Alexey Romanov's user avatar
25 votes
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 ...
Nathaniel's user avatar
  • 15.6k
24 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: ...
Bergi's user avatar
  • 608
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 ...
Pseudonym's user avatar
  • 22.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, ...
Josh Rumbut's user avatar
13 votes

Find 1s in almost all 0 array using comparisons only

Start by splitting the 100 elements in 50 pairs of two, and use a comparison on each pair. If a comparison returns -1 or 1, then you've found one of the elements which is 1 (and the other one must be ...
orlp's user avatar
  • 13.4k
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 ...
Evil's user avatar
  • 9,455
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 ...
Tom van der Zanden's 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 ...
Laakeri's user avatar
  • 1,339
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 ...
Steve Jessop's 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 ...
D.W.'s user avatar
  • 159k
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....
Nathaniel's user avatar
  • 15.6k
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 ...
Kelly Bundy's user avatar
6 votes

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 ...
subasri_'s user avatar
  • 169
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-...
Peter Cordes's user avatar
  • 1,055
5 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 ...
mousetail's user avatar
  • 166
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 ...
Nathaniel's user avatar
  • 15.6k
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'...
Draconis's user avatar
  • 7,138
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).
Daniel Mroz's 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 ...
reinierpost's user avatar
  • 5,539
4 votes
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})$ ...
John L.'s user avatar
  • 39k
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 ...
Jasmijn's user avatar
  • 161
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 ...
Caleb Stanford's user avatar
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 ...
gnasher729's user avatar
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 ...
John L.'s user avatar
  • 39k
4 votes

Can halting problem solved by soft computation?

No. ChatGPT is still just a program, although a rather large one.
Andrej Bauer's user avatar
  • 30.4k
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: $$ ...
Yuval Filmus's user avatar

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