## 6 Complexity Analysis of Image Classification with RRFs and SCNs
### RRFs  
A DT is a full binary tree of height \(H\). If each node involved in classifying a given image is a parameter, then the maximum number of nodes involved in the classification of single image is equal to exactly \(H\) (See Figure 4). Each DT has a specific LRF overlapped  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & **Min** & **Max** & **Mean** & **Num. Experiments** & **\% Mean Revisit** \\ \hline DQL1 & 78,352 & 78,779 & 78,630 & 28 & 21.370 \\ DQL2 & 78,480 & 78,834 & 78,633 & 28 & 21.367 \\ Total & 78,352 & 78,834 & 78,632 & 56 & 21.368 \\ \hline \hline \end{tabular}
\end{table}
Table 2: DQL state visitation experiments on all seven image datasets (BEE1, BEE2_1S, BEE2_2S, BEE3_S, BEE3_NS, BEE4, CIFAR-10); Min is minimum number of states in Q-Table in all experiments; Max is maximum number of states in Q-Table in all experiments; Mean is mean number states in Q-Table in all experiments; Mean % Revisit shows mean percent of states that are revisited; DQL method is described in Section 4.1.  
Figure 3: SCN architecture used in this investigation.  
with an image before the actual classification along a specific path begins. If \(IMG_{h}\) and \(IMG_{w}\) denote the height and width of the input image, then the number of parameters used in its classification is \(IMG_{h}\cdot IMG_{w}\), in the worst case.  
A trained DT \(T\) is a full binary tree of height \(H\). Thus, the maximum number of nodes in \(T\) is \(\sum_{i=0}^{H}2^{i}\). When \(T\) is used as an image classifier it thresholds exactly one pixel value along a specific path from the root to a leaf to determine the class of the image. Since thresholding requires 2 basic operations, the total number of operations \(T\) takes to classify an image is \(2H\), because at each node along the path a threshold decision is made on the value of a single pixel to go left or right (See Figure 4).  
Let us assume that an RRF \(F\) contains \(n\) DTs \(T_{1},...,T_{n}\) each of which has been trained to classify images into \(C\) classes with a specific LRF. Given an input \(h\times w\) image (i.e., of height \(h\) and width \(w\)), for each DT in \(F\), the image is overlapped with the DT's LRF. To perform the overlap, each pixel in the image is checked to see if it is present in the LRF's pixels, which requires \(h\cdot w\) operations. LRF overlapping is analogous to masking, because all pixels covered by the LRF retain their original values, whereas all other pixels are set to 0. If \(F\) contains \(n\) DTs, the number of overlap operations is \(n\cdot h\cdot w\).  
After LRF overlapping is done, \(F\) classifies the masked image with each \(T_{j}\), \(1\leq j\leq n\), to obtain \(n\) probability lists \(L_{1},...,L_{n}\), where \(L_{j}\) contains \(C\) probabilities computed by the corresponding \(T_{j}\) as the proportion of the training data covered by \(T_{j}\)'s leaf node reached on the input image from its root along a specific path (See Figure 4). The mean probability of each class, i.e., \(\mu\{L_{j}\}\), is computed, which requires \(n-1\) additions and \(1\) division, and the maximum \(\mu\{L_{j}\}\) is returned.  
If the maximum DT height in \(F\) is \(H_{max}\), then, in the worst case, the number of operations required to classify an image with \(F\), \(O_{RF}\), is given in Equation (2).  
\[O_{RF}=nhtw+2 nH_{max}+nC+2C=n(htw+2H_{max})+(n+2)C \tag{2}\]