sanket3280/code-execution
0
1/**2 * Complexity Analyzer - Estimates time and space complexity from execution data3 * Based on HackerEarth-style analysis with multiple input sizes4 */5 6/**7 * Estimate time complexity based on execution time ratios8 * @param {Array<{inputSize: number, timeMs: number}>} timeData - Array of execution times with input sizes9 * @returns {string} Estimated time complexity (e.g., "O(n)", "O(n²)", "O(n log n)")10 */11function estimateTimeComplexity(timeData) {12 if (!timeData || timeData.length < 2) {13 // If we have data but not enough to compare, analyze the single point14 if (timeData && timeData.length === 1) {15 return timeData[0].timeMs < 1 ? "O(1)" : "O(n)";16 }17 return "O(n)"; // Default assumption18 }19 20 // Sort by input size21 const sorted = [...timeData].sort((a, b) => a.inputSize - b.inputSize);22 23 // Calculate growth ratios24 const ratios = [];25 for (let i = 1; i < sorted.length; i++) {26 const sizeRatio = sorted[i].inputSize / Math.max(sorted[i - 1].inputSize, 1);27 const timeRatio = sorted[i].timeMs / Math.max(sorted[i - 1].timeMs, 0.001);28 ratios.push({ sizeRatio, timeRatio });29 }30 31 // Average time ratio32 const avgTimeRatio = ratios.reduce((sum, r) => sum + r.timeRatio, 0) / ratios.length;33 const avgSizeRatio = ratios.reduce((sum, r) => sum + r.sizeRatio, 0) / ratios.length;34 35 // Classify complexity based on growth pattern36 // O(1) - Constant: time doesn't grow with input37 if (avgTimeRatio < 1.2) return "O(1)";38 39 // O(log n) - Logarithmic: time grows slowly40 if (avgTimeRatio < Math.log2(avgSizeRatio) * 1.3) return "O(log n)";41 42 // O(n) - Linear: time grows proportionally43 if (Math.abs(avgTimeRatio - avgSizeRatio) < avgSizeRatio * 0.3) return "O(n)";44 45 // O(n log n) - Linearithmic: time grows slightly faster than linear46 if (avgTimeRatio < avgSizeRatio * Math.log2(avgSizeRatio) * 1.3) return "O(n log n)";47 48 // O(n²) - Quadratic: time grows with square of input49 const expectedQuadratic = Math.pow(avgSizeRatio, 2);50 if (Math.abs(avgTimeRatio - expectedQuadratic) < expectedQuadratic * 0.5) return "O(n²)";51 52 // O(2^n) or worse - Exponential53 if (avgTimeRatio > Math.pow(avgSizeRatio, 2) * 2) return "O(2^n)";54 55 // Default to O(n) if pattern is unclear56 return "O(n)";57}58 59/**60 * Estimate space complexity based on memory usage ratios61 * @param {Array<{inputSize: number, memoryKB: number}>} memoryData - Array of memory usage with input sizes62 * @returns {string} Estimated space complexity63 */64function estimateSpaceComplexity(memoryData) {65 if (!memoryData || memoryData.length < 2) return "O(1)"; // Default assumption66 67 // Sort by input size68 const sorted = [...memoryData].sort((a, b) => a.inputSize - b.inputSize);69 70 // Calculate growth ratios71 const ratios = [];72 for (let i = 1; i < sorted.length; i++) {73 const sizeRatio = sorted[i].inputSize / sorted[i - 1].inputSize;74 const memRatio = sorted[i].memoryKB / Math.max(sorted[i - 1].memoryKB, 1); // Avoid division by zero75 ratios.push({ sizeRatio, memRatio });76 }77 78 // Average memory ratio79 const avgMemRatio = ratios.reduce((sum, r) => sum + r.memRatio, 0) / ratios.length;80 const avgSizeRatio = ratios.reduce((sum, r) => sum + r.sizeRatio, 0) / ratios.length;81 82 // Classify complexity based on growth pattern83 // O(1) - Constant: memory doesn't grow with input84 if (avgMemRatio < 1.2) return "O(1)";85 86 // O(log n) - Logarithmic: memory grows slowly87 if (avgMemRatio < avgSizeRatio * 0.5) return "O(log n)";88 89 // O(n) - Linear: memory grows proportionally90 if (Math.abs(avgMemRatio - avgSizeRatio) < 0.5) return "O(n)";91 92 // O(n²) - Quadratic: memory grows with square of input93 if (avgMemRatio > avgSizeRatio * 2) return "O(n²)";94 95 // Default to O(1) if pattern is unclear (most algorithms use constant extra space)96 return "O(1)";97}98 99/**100 * Estimate input size from test case input101 * @param {string} input - Test case input (JSON format)102 * @returns {number} Estimated input size103 */104function estimateInputSize(input) {105 try {106 const parsed = JSON.parse(input);107 108 // Find the largest array or string in the input109 let maxSize = 1;110 111 const findSize = (obj) => {112 if (Array.isArray(obj)) {113 maxSize = Math.max(maxSize, obj.length);114 obj.forEach(findSize);115 } else if (typeof obj === 'string') {116 maxSize = Math.max(maxSize, obj.length);117 } else if (typeof obj === 'object' && obj !== null) {118 Object.values(obj).forEach(findSize);119 }120 };121 122 findSize(parsed);123 return maxSize;124 } catch (e) {125 // If parsing fails, estimate from string length126 return Math.max(1, Math.floor(input.length / 10));127 }128}129 130/**131 * Analyze source code for complexity patterns132 * @param {string} sourceCode - The source code to analyze133 * @returns {Object} Detected complexity patterns134 */135function analyzeSourceCode(sourceCode) {136 if (!sourceCode) return { timeComplexity: null, spaceComplexity: null };137 138 const code = sourceCode.toLowerCase();139 140 // Time Complexity Detection141 let timeComplexity = null;142 143 // O(2^n) - Exponential: recursive calls without memoization144 if ((code.match(/function.*\(.*\).*{[\s\S]*?\1\(/g) || []).length > 1 && 145 !code.includes('memo') && !code.includes('dp') && !code.includes('cache')) {146 timeComplexity = "O(2^n)";147 }148 // O(n³) - Cubic: three nested loops149 else if ((code.match(/for\s*\(|while\s*\(/g) || []).length >= 3) {150 const nestedLoops = (code.match(/for[\s\S]{0,200}for[\s\S]{0,200}for/g) || []).length;151 if (nestedLoops > 0) timeComplexity = "O(n³)";152 }153 // O(n²) - Quadratic: two nested loops154 if (!timeComplexity && (code.match(/for\s*\(|while\s*\(/g) || []).length >= 2) {155 const nestedLoops = (code.match(/for[\s\S]{0,200}for/g) || []).length;156 if (nestedLoops > 0) timeComplexity = "O(n²)";157 }158 // O(n log n) - Linearithmic: sorting or divide-and-conquer159 if (!timeComplexity && (code.includes('sort') || code.includes('mergesort') || code.includes('quicksort'))) {160 timeComplexity = "O(n log n)";161 }162 // O(n) - Linear: single loop163 if (!timeComplexity && (code.match(/for\s*\(|while\s*\(/g) || []).length >= 1) {164 timeComplexity = "O(n)";165 }166 // O(log n) - Logarithmic: binary search pattern167 if (!timeComplexity && (code.includes('binary') || (code.includes('while') && code.includes('/= 2')))) {168 timeComplexity = "O(log n)";169 }170 // O(1) - Constant: no loops171 if (!timeComplexity) {172 timeComplexity = "O(1)";173 }174 175 // Space Complexity Detection176 let spaceComplexity = null;177 178 // O(n²) - Quadratic space: 2D arrays179 if (code.match(/\[\s*\[/g) || 180 (code.includes('array') && code.match(/array.*array/gi))) {181 spaceComplexity = "O(n²)";182 }183 // O(n) - Linear space: arrays, lists, hash maps, objects184 else if (code.match(/=\s*\[\]/) || // const arr = []185 code.match(/=\s*\{\}/) || // const map = {}186 code.match(/=\s*new\s+(array|map|set)/i) || // new Map(), new Set()187 code.includes('array') || 188 code.includes('list') || 189 code.includes('dict') || 190 code.includes('hashmap') ||191 code.match(/const\s+\w+\s*=\s*\{\}/)) { // const obj = {}192 spaceComplexity = "O(n)";193 }194 // O(log n) - Logarithmic space: recursion depth195 else if (code.includes('return') && code.match(/function.*\(.*\).*{[\s\S]*?\1\(/g)) {196 spaceComplexity = "O(log n)";197 }198 // O(1) - Constant space: only variables199 else {200 spaceComplexity = "O(1)";201 }202 203 console.log('🔍 Source Code Analysis:');204 console.log(' Time Complexity:', timeComplexity);205 console.log(' Space Complexity:', spaceComplexity);206 console.log(' Code snippet:', code.substring(0, 200));207 208 return { timeComplexity, spaceComplexity };209}210 211/**212 * Analyze complexity from test case results213 * @param {Array} testCaseResults - Array of test case results with executionTime and memoryUsed214 * @param {string} sourceCode - Optional source code for static analysis215 * @returns {Object} Complexity analysis with time and space complexity216 */217function analyzeComplexity(testCaseResults, sourceCode = null) {218 if (!testCaseResults || testCaseResults.length === 0) {219 return {220 timeComplexity: "O(n)",221 spaceComplexity: "O(1)",222 avgTimeMs: 0,223 maxTimeMs: 0,224 avgMemoryKB: 0,225 maxMemoryKB: 0,226 performanceLog: generatePerformanceLog("O(n)", "O(1)", 0, 0)227 };228 }229 230 // Extract time and memory data with input sizes231 const timeData = [];232 const memoryData = [];233 234 testCaseResults.forEach(result => {235 if (result.executionTime !== null && result.executionTime !== undefined && result.executionTime > 0) {236 const inputSize = estimateInputSize(result.input || "{}");237 timeData.push({238 inputSize,239 timeMs: result.executionTime * 1000 // Convert seconds to ms240 });241 }242 243 if (result.memoryUsed !== null && result.memoryUsed !== undefined && result.memoryUsed > 0) {244 const inputSize = estimateInputSize(result.input || "{}");245 memoryData.push({246 inputSize,247 memoryKB: result.memoryUsed248 });249 }250 });251 252 // Calculate statistics253 const times = timeData.map(d => d.timeMs);254 const memories = memoryData.map(d => d.memoryKB);255 256 const avgTimeMs = times.length > 0 ? times.reduce((a, b) => a + b, 0) / times.length : 0;257 const maxTimeMs = times.length > 0 ? Math.max(...times) : 0;258 259 // Estimate complexities from execution data260 const executionTimeComplexity = estimateTimeComplexity(timeData);261 const executionSpaceComplexity = estimateSpaceComplexity(memoryData);262 263 // Analyze source code if provided (do this ONCE)264 const codeAnalysis = sourceCode ? analyzeSourceCode(sourceCode) : { timeComplexity: null, spaceComplexity: null };265 266 // Prefer code analysis over execution analysis (more accurate)267 const timeComplexity = codeAnalysis.timeComplexity || executionTimeComplexity;268 const spaceComplexity = codeAnalysis.spaceComplexity || executionSpaceComplexity;269 270 // Use estimated memory based on space complexity if no actual data271 let avgMemoryKB = memories.length > 0 ? memories.reduce((a, b) => a + b, 0) / memories.length : 0;272 let maxMemoryKB = memories.length > 0 ? Math.max(...memories) : 0;273 274 // If no memory data, estimate based on space complexity275 if (avgMemoryKB === 0) {276 if (spaceComplexity === 'O(n²)') {277 avgMemoryKB = 10240; // ~10MB for quadratic278 maxMemoryKB = 20480;279 } else if (spaceComplexity === 'O(n)') {280 avgMemoryKB = 2048; // ~2MB for linear281 maxMemoryKB = 4096;282 } else {283 avgMemoryKB = 512; // ~512KB for constant284 maxMemoryKB = 1024;285 }286 }287 288 return {289 timeComplexity,290 spaceComplexity,291 avgTimeMs: parseFloat(avgTimeMs.toFixed(2)),292 maxTimeMs: parseFloat(maxTimeMs.toFixed(2)),293 avgMemoryKB: parseFloat(avgMemoryKB.toFixed(2)),294 maxMemoryKB: parseFloat(maxMemoryKB.toFixed(2)),295 performanceLog: generatePerformanceLog(timeComplexity, spaceComplexity, avgTimeMs, avgMemoryKB)296 };297}298 299/**300 * Generate performance log in HackerEarth style301 * @param {string} timeComplexity - Estimated time complexity302 * @param {string} spaceComplexity - Estimated space complexity303 * @param {number} avgTimeMs - Average execution time in milliseconds304 * @param {number} avgMemoryKB - Average memory usage in KB305 * @returns {string} Formatted performance log306 */307function generatePerformanceLog(timeComplexity, spaceComplexity, avgTimeMs, avgMemoryKB) {308 return `------------------------------------------------------------309⚙️ Algorithm Performance Analysis310------------------------------------------------------------311🕒 Estimated Time Complexity : ${timeComplexity}312💾 Estimated Space Complexity : ${spaceComplexity}313📊 Avg Execution Time : ${avgTimeMs.toFixed(2)} ms314📈 Avg Memory Usage : ${(avgMemoryKB / 1024).toFixed(2)} MB315------------------------------------------------------------`;316}317 318module.exports = {319 estimateTimeComplexity,320 estimateSpaceComplexity,321 estimateInputSize,322 analyzeComplexity,323 analyzeSourceCode,324 generatePerformanceLog325};326