6 votes

Possible Mistake in Skiena's Algorithm Design Manual

You are totally right, though I think there is an easier proof: if $m = n$, then $mn-m^2 +m= m\notin \Omega(m^2)$. However, since the analysis is done when searching for a worst case, you could just ...
Nathaniel's user avatar
  • 13.9k
2 votes
Accepted

Prove the relation between space complexity and time complexity of the graph search which uses "the explored set"

The usage of "within" is a bit confusing, but I think it means the space complexity is never smaller than the time complexity divided by a factor of $b$. The space complexity of an algorithm ...
Discrete lizard's user avatar
  • 8,128
2 votes
Accepted

Find all the induced paths with a start vertex

Consider the following graph $G = (V, E)$ where: $V = \{v_0\}\cup \{u_1,…, u_n\}\cup \{v_1, …, v_n\}$; $E = \{\{v_0,u_1\}, \{v_0, v_1\}\}\cup \bigcup\limits_{k=1}^{n-1}\{\{u_k, u_{k+1}\}, \{u_k, v_{k+...
Nathaniel's user avatar
  • 13.9k
1 vote
Accepted

Quick sort with $K-1$ pivots

Hint: Suppose $k$ is a power of two at first, for simplicity. Find the $n/2$th element in the array. Then.... (you fill in the next part)
D.W.'s user avatar
  • 158k
1 vote
Accepted

Is bitonic sort order preserving on keys with the same value?

No. Consider an input of $n$ ones followed by $n$ zeroes to the bitonic network. This input is only affected by the network in the middle stage, where the order of elements is flipped. Thus the ...
fuz's user avatar
  • 911
1 vote

Ω(f(x)) and worst case analysis

One thing I would like to add is that $O$, $\Omega$, $o$, $\omega$, and $\Theta$ are all about relating functions to one another. In particular for functions $f$ and $g$, $f(x)\in O(g(x))$ says that (...
NaturalLogZ's user avatar
1 vote

Efficient streaming sort

Here is an algorithm to consider https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8982863/
Randomobserver's user avatar

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