-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathgetTimeComplexity.js
More file actions
59 lines (55 loc) · 1.48 KB
/
getTimeComplexity.js
File metadata and controls
59 lines (55 loc) · 1.48 KB
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
function getTimeComplexity(fn) {
let loopCount = 0;
let recurseCount = 0;
function countLoops(node) {
if (node.type === 'WhileStatement' || node.type === 'ForStatement' || node.type === 'DoWhileStatement') {
loopCount++;
}
if (node.body) {
if (Array.isArray(node.body)) {
node.body.forEach(countLoops);
} else {
countLoops(node.body);
}
}
}
function countRecurses(node) {
if (node.type === 'CallExpression' && node.callee.name === fn.name) {
recurseCount++;
}
if (node.arguments) {
node.arguments.forEach(countRecurses);
}
if (node.body) {
if (Array.isArray(node.body)) {
node.body.forEach(countRecurses);
} else {
countRecurses(node.body);
}
}
}
const ast = esprima.parseScript(fn.toString());
console.log('AST:', ast);
countLoops(ast);
countRecurses(ast);
console.log('Loop count:', loopCount);
console.log('Recursion count:', recurseCount);
if (recurseCount > 0) {
console.log('Time complexity: Exponential');
return 'Exponential';
} else if (loopCount > 0) {
if (loopCount === 1) {
console.log('Time complexity: Linear');
return 'Linear';
} else if (loopCount === 2) {
console.log('Time complexity: Quadratic');
return 'Quadratic';
} else {
console.log('Time complexity: Polynomial');
return 'Polynomial';
}
} else {
console.log('Time complexity: Constant');
return 'Constant';
}
}