Definition
O(√n) algorithms only need to check up to the square root of the data size N.
Key Characteristics
- ✓Check side(√N) instead of area(N)
- ✓Divisors always come in pairs
- ✓Efficient for prime checking
Use Cases
Used in these scenarios:
🛡️
Primality Test
Check divisibility up to √n
🔢
Finding Divisors
Divisors of 36: Check 1~6, pairs found automatically
📦
Sqrt Decomposition
Split array into √n blocks for range queries
🔄
Mo's Algorithm
Offline query processing using √n
Complexity
Time Complexity
Best
O(1)
Average
O(√n)
Worst
O(√n)
Space Complexity
O(1)
Understand Deeper with Visualization
See how the algorithm works through step-by-step animations and code execution.
Start Visualization