Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.
Before we go ahead and calculate the cyclomatic complexity of selection sort, let us revise cyclomatic complexity in general.
Cyclomatic complexity is a metric for calculating the number of linearly independent paths that run through a software program. Moreover, it helps us determine the complexity of the program and provides us with an
The steps used to calculate cyclomatic complexity include:
Control flow graph(CFG)
Cyclomatic Complexity = Edges - Nodes + 2p
Cyclomatic Complexity = # of Regions in the CFG
Cyclomatic Complexity = # of Predicate Nodes + 1
where:
The following is the code for selection sort. We can draw a control flow graph for this program from the code and each line’s corresponding line number.
void SelectionSort(int array1[]) {int size = array1.length;for (int i = 0; i < size-1; i++) {int minIndex = i;for (int j = i+1; j < size; j++)if (array1[j] < array1[minIndex])minIndex = j;int temp = array1[minIndex];array1[minIndex] = array1[i];array1[i] = temp;}}
Nodes have been labeled in the diagram, with respect to the code lines, for clear understanding.
Predicate Nodes are highlighted above in red in the CFG, i.e., the red colored nodes are predicate nodes. Pink-colored nodes represent the entry and exit points.
The number of regions in the CFG are:
Cyclomatic Complexity
Looking at the above CFG
Edges = 13, Nodes = 11, p = 1
Hence,
Cyclomatic Complexity = 13 - 11 + 2*1 = 4
Number of Regions in the CFG = 4
Hence,
Cyclomatic Complexity = 4
Predicate Nodes = 3
Hence,
Cyclomatic Complexity = 3 + 1 = 4
As demonstrated, all the formulas yield the same results. You may use any one of these to determine the cyclomatic complexity of selection sort. However, to sum it all up, the cyclomatic complexity of selection sort is 4.
RELATED TAGS
CONTRIBUTOR
Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.