GitHub

LoopSleuth vs Ruff vs Pylint: Quadratic Complexity Detection Comparison

Executive Summary

This comparison demonstrates that LoopSleuth successfully detects the intended quadratic complexity issues in tests/checks/quadratic.py, while both Ruff and Pylint fail to detect any of them.

Test File Overview

The test file tests/checks/quadratic.py contains:

  • 13 total functions
  • 6 functions with O(n²) (or worse) complexity (intentionally included as test cases)
  • 7 functions with optimal complexity (O(n), O(log n), etc.)

Results Summary

Tool Quadratic Issues Detected False Positives Success Rate
LoopSleuth 6/6 (100%) 0 ✅ 100%
Ruff 0/6 (0%) 0 ❌ 0%
Pylint 0/6 (0%) 0 ❌ 0%

Detailed Comparison

1. bubble_sort (line 1) - Nested loops over array

Issue: Classic O(n²) nested loop implementation

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):  # Nested loop = O(n²)
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
Tool Detected? Comments
✅ LoopSleuth YES Correctly identified nested loops and suggested using Python's built-in sort() with O(n log n) complexity
❌ Ruff NO Only flagged minor style issue: unnecessary start argument in range(0, ...)
❌ Pylint NO No warnings

2. find_duplicates (line 11) - Nested iteration

Issue: Comparing every pair of elements - O(n²)

def find_duplicates(nums):
    duplicates = []
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):  # O(n²) nested iteration
            if nums[i] == nums[j] and nums[i] not in duplicates:
                duplicates.append(nums[i])
    return duplicates
Tool Detected? Comments
✅ LoopSleuth YES Correctly identified O(n²) complexity and suggested using a set for O(n) solution
❌ Ruff NO No warnings about complexity
❌ Pylint NO Only suggested using enumerate (style, not performance)

3. sum_of_pairs - Checking all pairs

Issue: Nested loops over the same list = O(n²)

def sum_of_pairs(nums, target):
    pairs = []
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                pairs.append((nums[i], nums[j]))
    return pairs
Tool Detected? Comments
✅ LoopSleuth YES Correctly flagged nested loops
❌ Ruff NO No warnings
❌ Pylint NO No warnings

Additional quadratic examples in tests/checks/quadratic.py include matrix_multiply_naive, check_duplicates_naive, and contains_subsequence_slow.

What Ruff and Pylint Actually Found

Ruff (with --select ALL)

  • 52 warnings found, but NONE about complexity:
    • 📝 Missing type annotations (ANN001, ANN201, ANN204)
    • 📄 Missing/incorrect docstrings (D100, D107, D400, D415)
    • 🎨 Style issues (INP001, PIE808)
    • 🔢 Magic values (PLR2004)
    • Minor optimization: PERF401 on line 90 (use list.extend instead of append - NOT a quadratic complexity detection)

Verdict: Ruff focuses on code style and type safety, not algorithmic complexity.

Pylint

  • 4 warnings found, NONE about complexity:
    • 📄 Missing module docstring (C0114)
    • 🎨 Consider using enumerate instead of range(len(...)) (C0200) - 2 instances
    • 🎨 Unnecessary elif after return (R1705)
    • ⭐ Code quality score: 9.38/10

Verdict: Pylint focuses on code style and best practices, not algorithmic complexity.

Key Findings

✅ Why LoopSleuth Wins

  1. Purpose-Built for Complexity Detection: LoopSleuth uses LLM analysis specifically trained to understand algorithmic complexity
  2. Semantic Understanding: Analyzes code semantically, not just syntactically
  3. 100% Detection Rate: Found all 6 quadratic issues
  4. Actionable Solutions: Provides optimized code examples for each issue
  5. No False Positives: Correctly identified 7 efficient functions as OK

❌ Why Ruff and Pylint Fall Short

  1. Not Designed for This: Both tools focus on linting, style, and type safety - not algorithmic analysis
  2. Pattern-Based Only: They use pattern matching, which can't detect complex performance issues
  3. 0% Detection Rate: Missed ALL quadratic complexity issues
  4. Different Use Case: They're excellent for what they do, but complexity detection isn't their goal

Use Case Comparison

Use Case LoopSleuth Ruff Pylint
Detect O(n²) complexity ✅ Excellent ❌ No ❌ No
Type checking ❌ No ✅ Excellent ⚠️ Basic
Code style enforcement ❌ No ✅ Excellent ✅ Excellent
Suggest optimizations ✅ Yes ⚠️ Minor ⚠️ Minor
Docstring validation ❌ No ✅ Yes ✅ Yes
Code quality scoring ❌ No ❌ No ✅ Yes

Conclusion

LoopSleuth is demonstrably superior for detecting quadratic complexity issues, achieving a 100% detection rate compared to 0% for both Ruff and Pylint. While Ruff and Pylint are excellent tools for their intended purposes (linting, style, type safety), they are fundamentally not designed to detect algorithmic complexity issues.

For teams concerned about performance and scalability, LoopSleuth fills a critical gap that traditional linters cannot address.

Reproduction

To reproduce these results:

# Run LoopSleuth
./target/release/loopsleuth --model ./models/qwen2.5-coder-3b-instruct-q4_k_m.gguf tests/checks/quadratic.py
# Run Ruff (all rules)
ruff check tests/checks/quadratic.py --select ALL
# Run Pylint
pylint tests/checks/quadratic.py

Environment:

  • LoopSleuth: Latest version
  • Ruff: 0.14.14
  • Pylint: 4.0.4
  • Test file: tests/checks/quadratic.py

Read the original on github.com ↗