2 votes

Rank in a Convex Combination

By duality, this problem is equivalent to the halfplane range query problem. For the worst-case complexity, there is a known space-time tradeoff of [1]: $O(n^2/\log^2 n)$ data structure size and $O(\...
user avatar
  • 1,416
1 vote

Floyd's Cycle Detection Algorithm Proof In Laymen

Assume there is a cycle of length r, which is entered after m steps. Once you enter the cycle, you stay in the cycle. After either m steps, or after 1 step if m = r, both tortoise and hare are in the ...
user avatar
  • 25.6k
1 vote

Floyd's Cycle Detection Algorithm Proof In Laymen

1. Detecting cycle using Floyd's cycle detection algorithm - for this we need answer to the question: what's the guarantee that the hare and the tortoise will meet? 2. Detecting the starting point of ...
user avatar

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