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 ...
- 31.5k
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 ...
- 3,192
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 ...
- 16k
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: ...
- 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 ...
- 23.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, ...
- 241
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 ...
- 13.8k
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 ...
- 9,495
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 ...
- 13.4k
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 ...
- 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 ...
- 531
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.♦
- 164k
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....
- 16k
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 ...
- 412
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 ...
- 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-...
- 1,065
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 ...
- 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 ...
- 16k
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'...
- 7,176
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).
- 376
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 ...
- 5,776
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})$ ...
- 39.1k
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 ...
- 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 ...
- 7,158
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 ...
- 31.5k
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 ...
- 39.1k
4
votes
Can halting problem solved by soft computation?
No. ChatGPT is still just a program, although a rather large one.
- 31k
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:
$$
...
- 278k
Only top scored, non community-wiki answers of a minimum length are eligible