New answers tagged runtime-analysis
1
Your problem is known as the maximum diversity problem.
0
Big-O is an upper bound. $\log n = O(n^2)$, for example, so the answer is “no idea”.
If you used $\Theta$ then you know that for large n f(n) is between some bounds. You don’t know how large n will have to be, so we know nothing at all for $n = 10^5$.
For large n, f(n) is between $c_1 \cdot n^2$ and $c_2 \cdot n^2$. We don’t know how large $c_1$ and $c_2$ ...
1
The Big O notation is about the limiting behavior, thus it describes an upper bound of a function when the argument tends to a particular value or infinity.
In your case you have a fixed $n$, thus an upper bound of a number of operations for both loops is the same, namely $100000^2$, thus your algorithm is $O(1)$, consequently, both loops are equivalent in a ...
2
You can use quickselect, which has expected linear time complexity. (There's a version using the median-of-medians partitioning algorithm which has worst-case linear time complexity, but it's usually a lot slower in practice.) Note that if there are duplicate elements in the two arrays, it might not be possible to satisfy the strict less-than constraint ...
-1
Concatenate A and B into one array C with a total length of 2n. You start with the partition [1, 2n] of C with the goal to make the first l items less than the last r items, l = r = n initially.
As long as your partition has length 2 or more: Pick a random pivot element. Partition into two partitions of length x and y, like in quick sort. If x <= l then ...
1
You could sort them and then iterate over them. Sorting is $n\log n$ and then it would only take one more pass to go check them because once you've passed an element, you know you've done all the swapping you need for that element.
1
$O(n^2\log n)$ is better, since $\lim_{n \to \infty} {n^2\log n \over n^{2.32}} = 0$.
1
$O(n^{2.32})$ is kind of unusual. Do you have a mathematical proof for this, or is it an estimated based on observations? In that case, you can't draw any conclusions from it.
Big-Oh is an upper bound. So first you need to check what is the actual behaviour. If an algorithm runs in $O(n)$ then it is correct (but not very useful) to say it runs in $O(n^{2.32}...
1
I see, that answer is done and accepted, but let me share some thoughts:
Short answer: knowing only upper bounds it's impossible to compare algorithms. We can compare upper bounds, but this doesn't give answer to algorithms relation.
Long answer: assume we have $f\in O(n^2\log n)$ and $g \in O(n^{2.32})$. Because $\exists N \in \mathbb{N}$ such that for $n &...
1
You will need to compare the rate of change for both functions. This can be accomplished by taking the derivative of both functions:
$$ O_1'(n^2 log(n)) = \frac{d}{dn} n^2 log(n) = n + 2n × log(n) $$
$$ O_2'(n^{2.32}) = \frac{d}{dn} n^{2.32} = 2.32n^{1.32} $$
Plot these derivatives and compare the graphs. If they still seem too close, continue to take higher ...
Top 50 recent answers are included