40
votes
Accepted
Time complexity $O(m+n)$ Vs $O(n)$
Yes:
$n+m \le n+n=2n$ which is $O(n)$, and thus $O(n+m)=O(n)$
For clarity, this is true only under the assumption that $m\le n$. Without this assumption, $O(n)$ and $O(n+m)$ are two different things -...
- 11.8k
31
votes
Accepted
Array access is O(1) implies a fixed index size, which implies O(1) array traversal?
It's a good question. From a pragmatic perspective, we tend not to worry about it.
From a theoretical perspective, see the transdichotomous model. In particular, a standard assumption is that there ...
D.W.♦
- 169k
25
votes
How to find 5 repeated values in O(n) time?
The solution in fade2black's answer is the standard one, but it uses $O(n)$ space. You can improve this to $O(1)$ space as follows:
Let the array be $A[1],\ldots,A[n]$. For $d=1,\ldots,5$, compute $\...
- 281k
22
votes
Accepted
How to find 5 repeated values in O(n) time?
You could create an additional array $B$ of size $n$. Initially set all elements of the array to $0$. Then loop through the input array $A$ and increase $B[A[i]]$ by 1 for each $i$. After that you ...
- 9,895
12
votes
Accepted
Applicative-order languages don't support constant time array writes? If not, why not?
Skiena didn't say "applicative order", just "applicative". This is sometimes used as meaning something like "purely functional", or a language that evaluates via the application of functions as ...
- 12.2k
12
votes
Accepted
How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case?
What is meant by "lower bound" in this case is a lower bound on the worst-case number of comparisons. In this case, it happens to also be an upper bound.
The lower bound has to be something that is ...
- 13.5k
11
votes
Accepted
Find a point shared by maximum segments
Let's use $+$ to denote the start of a segment and $-$ to denote the end. For each segment, create two pairs, one for each endpoint:
...
- 3,479
11
votes
Time complexity $O(m+n)$ Vs $O(n)$
Yes, since $n + m \leq 2n$ the algorithm is $O(n)$. However, you may wish to write $O(m + n)$ because it clearly shows which variables the algorithm depends on, and what each variable does to the ...
- 211
11
votes
Accepted
Why does the order of the nested loops matter when solving the Coin Change problem?
In the second solution you are overcounting the number of combinations.
In fact you are counting the of ways to choose an ordered list of coins that sums to sum.
...
- 29.8k
8
votes
How to find 5 repeated values in O(n) time?
There's also a linear time and constant space algorithm based on partitioning, which may be more flexible if you're trying to apply this to variants of the problem that the mathematical approach doesn'...
- 992
8
votes
Accepted
Sorting a large list of test scores
This is a very easy question, assuming all scores are integers.
Here is the simplest algorithm in plain words. We will initiate count, an integer array of 100 ...
- 39.2k
7
votes
What is the time complexity of memory allocation assumed to be?
what would the worst-case complexity be if it didn't have to copy over $n$ items? If it only needed to allocate a buffer with size $O(n)$ when resizing, would that be considered to run $O(1)$ or $O(n)$...
- 13.5k
7
votes
Accepted
Name of this rearranging/sorting problem?
Note: It is a hardness proof, and I think there are practical algorithms like integer programming, etc.
Given a BIN_PACKING instance where you want to pack $K$ numbers $n_1,\ldots,n_K$ into $L$ bins ...
- 1,183
7
votes
Accepted
what is actually a circular array and representation
Circular array is just a fixed size array. We call it circular just because we define the operations on the array in such a manner that its limited size can be utilized again and again and it ...
- 1,215
7
votes
Is it possible to solve this problem in less than n^2 time without using additional space?
Let’s use $a_i$ for the array. You are interested in
$$
\begin{align*}
\max_{i,j} a_i + a_j + |i-j| &= \max_{i,j} a_i + a_j + \max(i-j,j-i) \\ &=
\max_{i,j} \max((a_i+i)+(a_j-j), (a_j+j)+(a_i-...
- 281k
7
votes
Accepted
Minimum number of increment / decrement operations to make an array distinct?
First Observation:
Consider the result array, which contains $N$ distinct numbers between 1 and $N$.
Since there are only $N$ numbers between 1 and $N$, all those numbers must appear in the result ...
- 39.2k
7
votes
Accepted
Arrays. Find row with most 1's, in O(n)
Below is an algorithm which runs in $\mathcal{O}(1)$ memory and $\mathcal{O}(n)$ time. It accepts a $n \times n$ matrix $A$ which is $1$-indexed, follows the constraint described in the problem, and ...
- 664
6
votes
How to measure "sortedness"
I have my own definition of "sortedness" of a sequence.
Given any sequence [a,b,c,…] we compare it with the sorted sequence containing the same elements, count number of matches and divide it by the ...
6
votes
Accepted
Finding duplicate in immutable array in linear time and constant space
Let us denote the array by $a_1,\ldots,a_{n+1}$. Define a function from $\{1,\ldots,n+1\}$ to itself as follows: $f(i) = a_i$. The graph of the function is a directed graph in which each node has ...
- 281k
6
votes
Accepted
Returning random integer from interval based on last result and a seed
I suggest you pick a random permutation on the range $[a,b]$, i.e., a bijective function $\pi:[a,b]\to [a,b]$. Then, maintain a counter $i$ that starts at $i=a$; at each step, output $\pi(i)$ and ...
D.W.♦
- 169k
6
votes
Why does the order of the nested loops matter when solving the Coin Change problem?
Why is the working solution correct?
First things first. Important things first. Let us understand why the working solution is correct first instead of finding where the wrong solution goes wrong.
...
- 39.2k
5
votes
How to find 5 repeated values in O(n) time?
Leaving this as an answer because it needs more space than a comment gives.
You make a mistake in the OP when you suggest a method. Sorting a list and then transversing it $O(n\log n)$ time, not $O(n^...
- 777
5
votes
To find median of $k$ sorted arrays of $n$ elements each in less than $O(nk\log k)$
Let us denote the arrays by $A_1,\ldots,A_k$, their sizes by $|A_1|,\ldots,|A_k|$, their medians by $m_1,\ldots,m_k$, and their union by $\mathbf{A}$. We will try to solve the following more general ...
- 281k
5
votes
Accepted
How is the formula for calculation in row/column major obtained?
Row-major order stores the rows of the array one after another in memory. That is, the array
a d g j
b e h k
c f i l
is stored as
...
- 82.6k
5
votes
Accepted
Maximum subarray of bounded length
The problem you are describing can be solved in $O(n)$.
Let's define the prefix sum as:
$$\text{psum}[i] = \sum_{0 \le j \le i} A[j]$$
Then your function can be expressed as:
$$\Phi(i, j) = \text{...
- 1,605
5
votes
Accepted
Which sort algorithm to choose given two specific arrays?
I believe the goal of this question was to get you to say that the information about even or odd can't lead to any significant speedup in runtime.
Suppose you have an algorithm which works very fast ...
- 2,552
5
votes
Accepted
Index variable takes up log(n) space?
If you have a variable $x$ that can represent any number from $0$ to $n-1$ (or any value from a set of of $n$ possible values, really), such an the index of an array of $A[0 \dots n-1]$ of $n$ ...
- 29.8k
5
votes
Accepted
Sort an array with a constant number of unsorted elements
Denote the array by $A_1,\ldots,A_n$. If $A_i > A_{i+1}$ then at least one of the two elements is out of place. We scan the array, and each time we find such a pair, we remove both elements. In $O(...
- 281k
5
votes
Array access is O(1) implies a fixed index size, which implies O(1) array traversal?
Big-O notation can be tricky because it hides details. Big-O describes a way to measure a function related to complexity. That function may be "number of memory accesses," which would ...
- 3,562
Only top scored, non community-wiki answers of a minimum length are eligible