Abstract: Dendritic cell algorithm (DCA) is inspired by functions of the dendritic cells (DCs) of the innate immune system,and has been successfully applied to numerous security-related problems.However,theoretical analysis of the DCA has barely been performed,and most theoretical aspects of the algorithm have not yet been revealed.Other immune inspired algorithms,such as negative and clonal selection algorithms,are theoretically presented in many literatures.As a result,it is important to conduct a similar theoretical analysis of the DCA,and determine its runtime complexity and other algorithmic properties in line with other artificial immune algorithms.Theoretical analysis was implemented via introduction of three runtime variables in terms of three phases of the algorithm.The standard DCA achieves a lower bound of Ω(n) runtime complexity and an upper bound of O(n²) runtime complexity under the worst case.In addition,the algorithm’s runtime complexity can be improved to O(max(nN,nδ)) by using segmentation approach for online analysis component.

Key words: Dendritic cells algorithm,Formal description,Runtime complexity