## 6 Complexity Analysis
### Time Complexity  
Time complexity (or time efficiency) is the measure of the amount of time taken by an algorithm to execute or run as a function of the input size. It is a way to describe how efficient an algorithm is in terms of the amount of time it takes to solve a problem. There are two known approaches:  
1. The **empirical approach** is used to measure time complexity experimentally, which has several limitations; for example, it depends on hardware resources, the software environment, and the implementation design;
2. The **analytical approach**, which encounters the limitations of the empirical approach and is independent of the computing hardware, programming languages, and complex detail of the algorithm. The execution time is estimated by counting the primitive operations of the statement for input values. In this study, we analyze both linking algorithms, i.e., CRMDL (Algorithm 1) and SMTW (Algorithm 2), using an analytical approach. Table 4 presents the time complexity of CRMDL, and subsequently present the time complexity of SMTW. \begin{table}
\begin{tabular}{l c c} \hline \hline
**Statement** & **Unit Cost** & **Total Cost** \\ \hline UNA Pre-processing & n & n \\ \hline T\({}_{u}\) = \{t\({}_{1}\), t\({}_{2}\), t\({}_{3}\),..., t\({}_{n}\)\} & n & n \\ \hline Remove stopwords (if any) & k & k \\ \hline
**for**\(t_{i}\in T_{u}\) _upto n_ & n + 1 & n + 1 \\ \hline Find tf for each term t from T & n & n \\ \hline Update Map(UNA) & 1 & 1 \\ \hline Map(UNA) = \{t\({}_{1}\), t\({}_{2}\), t\({}_{3}\),..., t\({}_{n}\)\} & n & n \\ \hline Identify the English meaning of each Urdu term in the dictionary & 1 & 1 \\ \hline Identify multiple meanings for each Urdu word (if any) & k & k \\ \hline
**for**\(ENA\in DNSA\)**do** & n + 1 & n + 1 \\ \hline T\({}_{e}\) = \{t\({}_{1}\), t\({}_{2}\), t\({}_{3}\),..., t\({}_{n}\)\} & n & n \\ \hline Remove stopwords (if any) & k & k \\ \hline
**for**\(t_{i}\in T_{e}\) _upto m_ & \(\sum\limits_{i=1}^{n}({\rm m}_{i})\) & n * \(\sum\limits_{i=1}^{n}({\rm m}_{i})\) \\ \hline Find tf for each term t from T & n & n \\ \hline Update Map(ENA) & 1 & 1 \\ \hline Map(ENA) = \{(t\({}_{1}\), w\({}_{1}\)), (tf\({}_{2}\), w\({}_{2}\)), (tf\({}_{3}\), w\({}_{3}\)),..., (tf\({}_{j}\), w\({}_{j}\))\} & n & n \\ \hline Map(ENA) = \{(t\({}_{1}\), w\({}_{1}\)), (tf\({}_{2}\), w\({}_{2}\)), (tf\({}_{3}\), w\({}_{3}\)),..., (tf\({}_{j}\), w\({}_{j}\))\} & n & n \\ \hline Map(UNA) = \{(t\({}_{1}\), w\({}_{1}\)), (tf\({}_{2}\), w\({}_{2}\)), (tf\({}_{3}\), w\({}_{3}\)),..., (tf\({}_{i}\), w\({}_{j}\))\} & n & n \\ \hline CT = \{t\({}_{1}\) + tf\({}_{2}\)W\({}_{1}\) + (tf\({}_{1}\) + tf\({}_{2}\))W\({}_{2}\) +... + (tf\({}_{1}\) + tf\({}_{2}\))W\({}_{cur}\)} & \(\sum\limits_{i=1}^{cur}({\rm tf}_{1}+{\rm tf}_{2})\)W\({}_{i}\) & \(\sum\limits_{i=1}^{cur}({\rm tf}_{1}+{\rm tf}_{2})\)W\({}_{i}\) \\ \hline UT = \{t\({}_{1}\) \(\vee\) tf\({}_{2}\))W\({}_{1}\) + (tf\({}_{1}\) \(\vee\) tf\({}_{2}\))W\({}_{2}\) +... + (tf\({}_{1}\) \(\vee\) tf\({}_{2}\))W\({}_{nur}\)} & \(\sum\limits_{j=1}^{cur}({\rm tf}_{1}\) \(\vee\) tf\({}_{2}\))W\({}_{j}\) & \(\sum\limits_{j=1}^{cur}({\rm tf}_{1}\) \(\vee\) tf\({}_{2}\))W\({}_{j}\) \\ \hline TT = UT + CT & 1 & 1 \\ \hline CRMDL = CT/TT & 1 & 1 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Time complexity of CRMDL.