Complexity analyzer for Golang

• Inline complexity hints - Displays time complexity on every loop and function call
• Overall complexity summary - Shows Time: O(n log n) | Space: O(n) at the top of your file
• Comprehensive pattern detection - 100+ Go patterns including stdlib, algorithms, and data structures
• Nested operation support - Correctly handles sort inside loops, multiple nested structures
• Per-function analysis - Shows complexity for each function with time and space
• Zero dependencies - Fully offline, no external tools required

• Loops: traditional for i:=0; i<n; i++, range-based for _, v := range, condition-based for condition, infinite for { }, and constant-bound for i := 0; i < 10; i++ → O(1)
• Logarithmic loops: i *= 2, i /= 2, i <<= 1, i >>= 1, i += i → O(log n)
• Square root loops: i * i <= n condition → O(√n)
• Nested complexity multiplication: correctly computes O(n²), O(n³), O(n log n), O(n² log n), O(n² log log n), O(log² n), O(n√n), O(n × 2^n), O(n × n!)
• Sorting: sort.Slice, SliceStable, Ints, Strings, Search -> O(log n), sort.SearchInts, SearchFloat64s, IsSorted, IntsAreSorted -> O(n), sort.Reverse -> O(1)
• Containers: container/list.New, PushBack, PushFront, Remove -> O(1), container/ring.New, Len, Move -> O(n), container/heap.Init -> O(n), container/heap.Push, Pop -> O(log n)
• Strings: strings.Split, Join, Contains, Index, ToLower, ToUpper, Trim, Replace, Count, HasPrefix, HasSuffix -> O(n)
• Bytes: bytes.Split, Join -> O(n), bytes.Equal, Compare -> O(n), bytes.NewBuffer -> O(1), bytes.Buffer.WriteString -> O(n)
• Math: math.Abs, Max, Min, Ceil, Floor, Round, Pow, Sqrt, Log, Exp, Sin, Cos, Tan, Atan2, Pi -> O(1), math/bits.OnesCount, LeadingZeros, TrailingZeros, RotateLeft -> O(1), math/big.NewInt -> O(1), big.Int.Add, Mul, Div, Sub -> O(n)
• I/O: fmt.Print, Println, Printf -> O(n), fmt.Sprint, Sprintf, Errorf -> O(n), fmt.Scan, Fscan, Sscan, Scanf -> O(n), os.Open, Create, Stat, Lstat, ReadFile, WriteFile, Read, Write, ReadDir -> O(n), bufio.NewReader, NewWriter, NewScanner -> O(1), io.ReadFull, Copy -> O(n)
• Encoding: json.Marshal, Unmarshal -> O(n), encoding/binary.Read, Write, LittleEndian -> O(n), base64.NewDecoder, NewEncoder -> O(n)
• Hashing: crypto/sha256.New, Sum256 -> O(n), crypto/md5.Sum -> O(n), hash.New -> O(n), hash.Hash.BlockSize, Size -> O(1)
• Concurrency: go goroutines, buffered/unbuffered channels -> O(1)
• Context: context.Background, TODO, WithTimeout, WithCancel, WithDeadline -> O(1)
• Filepath: filepath.Walk, Match, WalkDir -> O(n), filepath.Abs, Base, Clean, Ext, Join -> O(n)
• Reflect: reflect.DeepEqual -> O(n), reflect.TypeOf, ValueOf -> O(1)
• Random: rand.Shuffle, Perm -> O(n)
• Sync: sync.Map.Range -> O(n), sync.Map.Load, Store, Delete -> O(1), sync.Mutex.Lock, Unlock -> O(1), sync.Pool.Get, Put -> O(1), sync.WaitGroup.Add, Done, Wait -> O(n), sync.Once.Do -> O(1)
• Unicode/UTF8: utf8.DecodeRuneInString, RuneCountInString, ValidString -> O(n)
• Strconv: strconv.Atoi, Itoa, ParseInt, FormatInt -> O(n)
• Regexp: regexp.Compile, MustCompile -> O(n), regexp.MatchString, Find, FindAllString, ReplaceAllString -> O(n)
• Compress: gzip.NewWriter, NewReader -> O(n)
• Slices & Maps: slices.Sort, SortFunc, SortStableFunc -> O(n log n), slices.BinarySearch, BinarySearchFunc -> O(log n), slices.Contains, Equal, Clone, Delete, Insert, ContainsFunc, IndexFunc, Index -> O(n), maps.Keys, Values, Equal, Clone, Copy -> O(n)
• Builtins: append, delete, len, cap -> O(1), copy -> O(n), make (allocations -> O(n), capacity-only -> O(1))
• Time: time.Now, Sleep, Since, Until, Second, Hour -> O(1)
• Algorithms:
  • Graph: DFS O(V+E), BFS O(V+E), Dijkstra O(E log V), Bellman-Ford O(V×E), Floyd-Warshall O(n³), Topological Sort O(V+E), Kruskal's MST O(E log E), Prim's MST O(V²)
  • Sorting: Merge Sort O(n log n), Quick Sort O(n log n), Heap Sort O(n log n)
  • Data structures: Union-Find/DSU O(α(n)), Trie O(L), Segment Tree O(log n)
  • String matching: KMP O(n)
  • Dynamic Programming: Kadane's O(n), Longest Common Subsequence (LCS) O(n×m), 0/1 Knapsack O(n×W)
  • Number theory: Sieve of Eratosthenes O(n log log n), GCD O(log n)
  • Data structures: Binary Indexed Tree (Fenwick) O(log n), Sparse Table O(n log n) preprocessing / O(1) query
  • Searching: Binary Search O(log n)

• Slices: make([]int, n), make([]int, 0, n) -> O(n)
• Maps: make(map[K]V) -> O(n)
• Channels: make(chan T), make(chan T, buffer) -> O(n) for buffered, O(1) for unbuffered
• Allocations: new(Type) → O(1)
• 2D structures: make([][]int, n) → O(n²), make([]map[K]V, n) → O(n²)
• Correctly excludes function signature parameters (references, not allocations)
• Correctly excludes small slice/map literals ([]int{1, 2, 3})
• Correctly identifies O(1) for functions without allocations

• Neovim 0.11+
• Treesitter (Main branch / Neovim built-in)
• Go treesitter parser installed (:TSInstall go)

-- lazy.nvim
{
  'sjclayton/goplexity.nvim',
  ft = { 'go' },
}

:Goplexity              " Toggle complexity hints (analyze + show/hide)
:Goplexity constraints 100000 2000 256  " Set problem constraints (n, time_ms, memory_mb)

Running :Goplexity toggles hints on and off. Each time hints are shown, the buffer is re-analyzed so results are always fresh.

package main                    // 🧠 Time: O(n²) | Space: O(n)

import "sort"

func solve(n int) {             // 🧠 Time: O(n²) | Space: O(n)
    arr := make([]int, n)           // 🧠 T:O(n)
    for i := 0; i < n; i++ {        // 🧠 T:O(n) S:O(1)
        arr[i] = i
    }

    sort.Slice(arr, func(i, j int) bool {  // 🧠 T:O(n log n)
        return arr[i] < arr[j]
    })

    for i := 0; i < n; i++ {        // 🧠 T:O(n) S:O(1)
        for j := i + 1; j < n; j++ { // 🧠 T:O(n²) S:O(1)
            println(arr[i] + arr[j])
        }
    }
}

When n, time_limit_ms, and/or memory_limit_mb are set via :Goplexity constraints or setup(), the plugin warns if the detected complexity may exceed your limits:

⚠️  Time: O(n²) (~1.00e+11 ops) may exceed limit (1000ms)
⚠️  Space: O(n²) (~250000000.0 MB) may exceed limit (256MB)

require('goplexity').setup({
  virtual_text_icon = '🧠',
  virtual_text_hl_group = 'Comment',
  enabled = true,
  constraints = {
    n = nil,
    time_limit_ms = nil,
    memory_limit_mb = nil,
  },
  thresholds = {
    time_warning = 1e8,
    space_warning = 256,
  },
})

vim.keymap.set('n', '<leader>tc', ':Goplexity<CR>', { desc = 'Toggle complexity hints' })

Other plugins can toggle Goplexity and check its status via the return value:

local goplexity = require('goplexity')

-- Toggle hints (returns true if shown, false if hidden)
-- Re-runs analysis each time hints are shown
local visible = goplexity.toggle()

The plugin includes two test suites run headlessly via Neovim:

# Main suite: 73 tests covering all audited algorithm/syntax patterns
nvim --headless --clean --cmd "set rtp+=~/.local/share/nvim/site" -u tests/test_runner.lua 2>&1

# Integration suite: 80 tests covering (constraint warnings,
# memory limits, randomized testing, general functionality)
nvim --headless --clean --cmd "set rtp+=~/.local/share/nvim/site" -u tests/test_constraints_e2e.lua 2>&1

Each test fixture in tests/*/main.go is a real Go file with expected complexity declared in comments. The test runner analyzes each file and verifies the output matches expectations.

Anyone who wishes to help improve this plugin is welcome to open an issue and/or submit a pull request.