# Parallelization of the Honeybee Search Algorithm for Object Tracking
## 3 Results
### Polynomial Time Complexity  
The time complexity of NCC is obtained by observing Equations (11), (12) and (13). The time it takes to get \(\tilde{t}\) using Equation (13) is of \(O(m\times n)\). The next term \(\tilde{I}_{u,v}\) is also obtained in a time of \(O(m\times n)\). Finally, \(\gamma(u,v)\) is computed using three different summations, each of them require \(O(m\times n)\). To conclude, the time complexity of computing \(\gamma(u,v)\) for a single point \((u,v)\) is \(O(m\times n)\). Sequential exhaustive NCC requires to compute every single possible \(\gamma(u,v)\) for every \((u,v)\). This is the size of the feasible region \((w-m)\times(h-n)\). So \(O(m\times n)\times O((w-m)\times(h-n))=O(-m^{2}nh+mnwh+m^{2}n^{2}-mn^{2}w)=O( mmwh)\), note that \(mnwh\) is the greatest term because \(m\) should be smaller or equal to \(w\) and \(n\) should be lesser or equal to \(h\) (as illustrated in Figure 1). This is the time complexity of sequential exhaustive NCC (Table 2 row 1). In exhaustive parallel NCC, the GPU performs the computation of several \(\gamma(u,v)\) simultaneously. Let \(c\) be the maximum number of simultaneous work-items of the GPU, then the time complexity of parallel exhaustive NCC is \(O(\frac{mnwh}{c})\) (Table 2 row 2). HSA time complexity can be obtained observing the pseudocode in Figures 1-3; and Equations (1) and (2). Please note that this analysis is specific to the case where the fitness \begin{table}
\begin{tabular}{c c c} \hline \hline
**Implementation** & **Abbreviation** & **Time Complexity** \\ \hline Sequential exhaustive NCC & CPU NO BEE & \(O(mnwh)\) \\ Parallel exhaustive NCC & GPU NO BEE & \(O(\frac{mnwh}{c})\) \\ Sequential HSA NCC & CPU BEE & \(O(g\lambda_{h}mn)\) \\ Parallel HSA NCC & GPU BEE & \(O(\frac{gmm}{q})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Time Complexity of different implementations to be comparedfunction is \(\gamma(u,v)\), if the fitness function experiences any change, then so does the time complexity. The first line of the Exploration pseudocode takes \(O(\mu_{e})\), as it is a constrained random generation of \(\mu_{e}\) individuals. The second line of the exploration pseudocode has a time complexity of \(O(\mu_{e}mn)\) since \(\gamma(u,v)\) is computed for every one of the \(\mu_{e}\) individuals. Next, the time for line 4 is of \(O(\lambda_{e})\) and \(O(\lambda_{e}mn)\) for line 5; line 6 is omitted (no sharing). Exploration line 7 performs sorting, taking \(O((\mu_{e}+\lambda_{e})\text{log}(\mu_{e}+\lambda_{e}))\). In total, lines 4-7 have a time complexity of \(O(\lambda_{e}mn)\), since line 5 should be significantly slower to compute. This \(O(\lambda_{e}mn)\) time complexity operation is repeated several times (line 3), this number is called the maximum number of generations or \(g\), producing a time complexity of \(O(g\lambda_{e}mn)\) which is polynomially greater than the cost of lines 1-2. Thus, the exploration phase takes \(O(g\lambda_{e}mn)\). The recruitment phase requires the summation of the fitness of all the \(\mu_{e}\) individuals (Equation (1)) and then Equation (2) has to be computed for each of those individuals, producing a time complexity of \(O(\mu_{e})\). The harvest phase is very similar to the exploration phase; the key difference is the size of the evaluated populations (\(\mu_{h}\) and \(\lambda_{h}\)) resulting in time complexity of \(O(g\lambda_{h}mn)\). In polynomial terms, the greatest time complexity between exploration, recruitment, and harvest phases is that of the harvest phase given that it should be true that \(\lambda_{h}>\lambda_{e}\); taking those considerations the time complexity for sequential HSA NCC (Table 2 row 3) is of \(O(g\lambda_{h}mn)\) time complexity. The parallelization of HSA is described in Section 2.5.4. The evaluation of the fitness function \(\gamma(u,v)\) for each individual is performed by \(q\) work-items simultaneously. Please note that all individuals are processed in parallel because the number of individuals is \(p/q\), and this is dependent on the capacity of the GPU.