1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#![cfg_attr(coverage_nightly, coverage(off))]
//! Big-O Complexity Analysis Data Structures - Phase 5
//!
//! Provides memory-efficient representations for algorithmic complexity bounds,
//! supporting time and space complexity analysis with confidence scoring.
use serde::{Deserialize, Serialize};
use std::fmt;
/// Big-O complexity class enumeration
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[repr(u8)]
pub enum BigOClass {
/// O(1) - Constant time
Constant = 0,
/// O(log n) - Logarithmic time
Logarithmic = 1,
/// O(n) - Linear time
Linear = 2,
/// O(n log n) - Linearithmic time
Linearithmic = 3,
/// O(n²) - Quadratic time
Quadratic = 4,
/// O(n³) - Cubic time
Cubic = 5,
/// O(2^n) - Exponential time
Exponential = 6,
/// O(n!) - Factorial time
Factorial = 7,
/// Unknown or too complex to determine
Unknown = 255,
}
/// Input variable for complexity analysis
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[repr(u8)]
pub enum InputVariable {
/// Size of primary input (n)
N = 0,
/// Size of secondary input (m)
M = 1,
/// Number of unique elements (k)
K = 2,
/// Depth or height parameter (d)
D = 3,
/// Custom or composite variable
Custom = 255,
}
/// Flags for complexity bound properties
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize)]
#[repr(transparent)]
pub struct ComplexityFlags(u8);
/// Memory-efficient complexity bound representation (8 bytes)
#[repr(C, align(8))]
#[derive(Debug, Clone, Copy, Serialize, Deserialize)]
pub struct ComplexityBound {
/// Big-O complexity class (1 byte)
pub class: BigOClass,
/// Coefficient multiplier (2 bytes)
pub coefficient: u16,
/// Input variable (1 byte)
pub input_var: InputVariable,
/// Confidence percentage 0-100 (1 byte)
pub confidence: u8,
/// Property flags (1 byte)
pub flags: ComplexityFlags,
/// Padding for alignment (2 bytes)
_padding: [u8; 2],
}
/// Cache complexity characteristics
#[repr(C, align(8))]
#[derive(Debug, Clone, Copy, Serialize, Deserialize)]
pub struct CacheComplexity {
/// Cache hit ratio (0-100%)
pub hit_ratio: u8,
/// Cache miss penalty factor
pub miss_penalty: u8,
/// Working set size class
pub working_set: BigOClass,
/// Flags for cache behavior
pub flags: u8,
/// Padding for alignment
_padding: [u8; 4],
}
/// Recurrence relation for recursive algorithms
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct RecurrenceRelation {
/// Number of recursive calls per invocation
pub recursive_calls: Vec<RecursiveCall>,
/// Non-recursive work complexity
pub work_per_call: ComplexityBound,
/// Base case size
pub base_case_size: u32,
}
/// A single recursive call description
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct RecursiveCall {
/// Factor by which input size is reduced (e.g., n/2 has factor 2)
pub division_factor: u32,
/// Constant reduction in size (e.g., n-1 has reduction 1)
pub size_reduction: u32,
/// Number of such calls
pub count: u32,
}
/// Complexity proof type
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub enum ComplexityProofType {
/// Formally verified using theorem prover
Verified,
/// Validated through empirical testing
Empirical,
/// Based on pattern matching heuristics
Heuristic,
/// Unknown or unproven
Unknown,
}
// Impl blocks for BigOClass, InputVariable, ComplexityFlags,
// and their Display trait implementations
include!("complexity_bound_impls.rs");
// Impl blocks for ComplexityBound, CacheComplexity, RecurrenceRelation,
// and their Default/Display trait implementations
include!("complexity_bound_core.rs");
// Unit tests and property tests
include!("complexity_bound_tests.rs");