New answers tagged

0

Yes, you can solve the two-sum problem in $O(n)$ time, if the numbers are presented in sorted order. See my other answer for how to do it; it involves a linear scan. This is asymptotically optimal, as it already takes $O(n)$ time even to read the input, and solving the problem may require reading the entire input, so there can no further asymptotic ...


0

This can be solved in $O(n \log n)$ time, much like the ordinary two-sum problem. Sort the items by increasing capacity. Let $t$ denote the desired target (the total capacity), $t$ the amount you can go up or down, so our desired target range is $[t-u,t+u]$, and $A$ the array of elements. We will do a linear scan over the items, left-to-right. Suppose our ...


0

Create a Set searchSet to store the item's that have already been examined. Iterate through the input Array of item capacities. 2a. Find the targetCapacity for the current item: totalCapacity - itemCapacity. 2b. Generate a targetCapacitiesArray plus and minus the totalCapacity and the range allowance provided. 2c. For each capacity in targetCapacitiesArray, ...


0

The Two Sum solution can be optimized for runtime performance given the input Array is pre-sorted in ascending or descending order. If Binary Search is used to find the targetCapacity above, it will run in logarithmic, $O(logn)$, average runtime. This is faster than the pseudocode above that runs in linear, $O(n)$, runtime using iteration and hashing. If ...


0

The worst case for Quicksort happens when each partitioning divides an array of size n into sub arrays of size 1 and n-1. In your case, is that possible? Why isn’t it possible? What is the worst outcome of partitioning if the pivot is the median of 2k numbers? So what is the worst case in your algorithm?


0

In machine learning, there's often no clear "why" or "reason" we can point to. These are different methods, which implicitly embed different biases or different priors or different assumptions, and thus will work better in different situations.


1

The complexity of your algorithm on $n \times n$ matrices satisfies the recurrence $$ T(n)=nT(n-1) + O(n^3), $$ with a base case of $T(1) = O(1)$. In particular, $T(n) \geq n! T(1)$. In the other direction, let $S(n) = T(n)/n!$. Then $$ S(n) = S(n-1) + O(n^3/n!), $$ with a base case of $S(1) = O(1)$. Since $\sum_{n=0}^\infty n^3/n!$ converges, we get $S(n) = ...


0

From $f(n) = \Theta(g(n))$ you know that, for some positive constants $c \in \mathbb{R}^+$ and $\eta \in \mathbb{N}$, and for all $n \ge \eta$, it holds that $f(n) \ge c g(n)$, i.e., $g(n) \le \frac{1}{c} f(n)$.$^1$ Moreover, from $f(n) = o(h(n))$, you know that for any constant $c' > 0$ there is some $\eta'_{c'}$ such that $f(n) \le c' h(n)$ for any $n \...


2

Let us assume that $n$ is of the form $2^{2^k}$, and furthermore, a base case of $T(2) = 1$. Applying the substitution method, \begin{align} T(2^{2^k}) &= 1 + 2^{2^{k-1}} T(2^{2^{k-1}}) \\ &= 1 + 2^{2^{k-1}} + 2^{2^{k-1}+2^{k-2}} T(2^{2^{k-2}}) \\ &= 1 + 2^{2^{k-1}} + 2^{2^{k-1}+2^{k-2}} + 2^{2^{k-1}+2^{k-2}+2^{k-3}} T(2^{2^{k-3}}) \\ &= \...


0

Let's see what the algorithm does in its first few iterations: Mark all elements other than 1 as "potentially prime". Mark all multiples of 2, starting at 4, as "not prime". Mark all multiples of 3, starting at 9, as "not prime". Skip 4, since it is known to be not prime. Mark all multiples of 5, starting at 25, as "not ...


Top 50 recent answers are included