## 4 Proposed Approach
### Computational Complexity Analysis of the Threshold Active Learning Approach  
The time-complexity (big-\(\mathcal{O}\) notation) of Algorithm 1 is expressed in Equation (6), where \(\mathcal{O}(OPT(DB,T_{j})\) is the complexity of the **OPTIMIZE** procedure (Algorithm 3), \(J\) is the number of unlabeled datasets, and \(\mathcal{O}(AL(M_{j-1},DB,T_{j}))\) is the complexity of the **ACTIVE-LEARNING** procedure (Algorithm 2). \[\mathcal{O}(\mathrm{OPT}(DB,T_{j}))+J\cdot\mathcal{O}(\mathrm{AL}(M_{j-1},DB, T_{j})) \tag{6}\]The complexity \(\mathcal{O}(OPT(DB,T_{j})\) of the **OPTIMIZE** sub-algorithm (Algorithm 3) can be approximated by considering the main operations within the while loop and the nested for loop, as follows:  
* The complexity of training the model \(\textbf{LEARNING}(M_{j},DB)\) depends on the learning algorithm used based on the pre-trained model. Suppose it is \(\mathcal{O}(L(DB))\). * The complexity of testing the model \(\textbf{TEST}(M_{j},T_{j})\) depends on the size of the test set. Suppose it is \(\mathcal{O}(T(T_{j}))\). * The for loop has a complexity of \(\mathcal{O}(\|DB\|)\) to iterate over the dataset and compute the neural network output. Therefore, the complexity of the **OPTIMIZE** sub-algorithm for \(k\) iterations, where \(K\) is the maximum number of epochs, is approximately  
\[\mathcal{O}(OPT(DB,T_{j})=\mathcal{O}(K)\times(\mathcal{O}(L(DB))+\mathcal{O} (T(T_{j}))+\mathcal{O}(\|DB\|)) \tag{7}\]  
Similarly, to calculate the complexity \(\mathcal{O}(AL(M_{j-1},DB,T_{j}))\) of the **ACTIVE-LEARNING** sub-algorithm, we can consider the main operations within the for loop and the invoked functions:  
* **For loop:*
* The complexity of iterating over the test dataset \(T_{j}\) is \(\mathcal{O}(\|T_{j}\|)\). * Within the loop, the operation \(M_{j}(x_{q})\) has a complexity dependent on the selected pre-trained model, which can be considered \(\mathcal{O}(M)\). * The operations of comparison and updating the ambiguous set have a constant complexity \(\mathcal{O}(1)\). * **Human labeling and updating \(DB\):*
* The function \(\textbf{HUMAN\_LABEL}(AM_{k})\) will depend on the time taken by human experts but can be considered to be \(\mathcal{O}(\|AM_{k}\|)\) in the worst case. * The operation of updating the dataset \(DB\gets DB\cup AM_{k}\) has a complexity of \(\mathcal{O}(\|AM_{k}\|)\). * **Re-optimization of the model:*
* The complexity of the function \(\textbf{OPTIMIZE}(M_{j},DB,DB)\) is the same as that of the **OPTIMIZE*
* sub-algorithm, denoted as \(\mathcal{O}(\text{OPT}(DB))\), shown previously. Therefore, the complexity of the **ACTIVE-LEARNING*
* sub-algorithm is approximately \[\mathcal{O}(AL(M_{j-1},DB,T_{j}))=\mathcal{O}(\|T_{j}\|)\times\mathcal{O}(M) +\mathcal{O}(\|AM_{k}\|)+\mathcal{O}(\text{OPT}(DB))\] (8)  
Then, to determine the general big-\(\mathcal{O}\) order of the complexity of the **MAIN** algorithm (Algorithm 1), we need to observe the dominant terms in the total complexity expression, \(\mathcal{O}(MAIN())\), and simplify them:  
1. Complexity of training and testing (**OPTIMIZE**): * \(\mathcal{O}(K)\times\mathcal{O}(L(DB))\); * \(\mathcal{O}(K)\times\mathcal{O}(T(T_{j}))\); * \(\mathcal{O}(K)\times\mathcal{O}(\|DB\|)\). 2. Complexity of **ACTIVE-LEARNING**: * \(\mathcal{O}(\|T_{j}\|\cdot M)\); * \(\mathcal{O}(\|AM_{k}\|)\); * \(\mathcal{J}\times\mathcal{O}(K)\times(\mathcal{O}(L(DB))+\mathcal{O}(T(T_{j})) +\mathcal{O}(\|DB\|))\). We assume that:  
* \(\mathcal{O}(L(DB))\) is the complexity of training (the **LEARNING** procedure in Algorithm 3), which can be very high if the model is complex. * \(\mathcal{O}(T(T_{j}))\) is the complexity of testing, generally lower than that of training. * \(\mathcal{O}(M)\) is the complexity of obtaining the model output, which may depend on the number of layers and parameters of the neural network model. * \(\mathcal{O}(\|DB\|)\) and \(\mathcal{O}(\|T_{j}\|)\) are proportional to the sizes of the training and test datasets. Generally, training (and thus the **OPTIMIZE** procedure) will be the most expensive operation.