A complexidade do tempo é geralmente definida como o "número de operações no pior dos casos para uma máquina de Turing". O modelo de computação de circuito monótono não é o modelo de tempo de Turing. Portanto, não faz sentido dizer qual é a complexidade do tempo de um circuito desse tipo.
Por outro lado, se vemos o modelo de circuito monótono como um modelo de circuitos reais, então um "custo de tempo" da computação é a profundidade de tal circuito. Assim, nesse sentido, a complexidade de tempo do circuito mencionado é de 5,3log (n).
É claro que, em circuitos reais, existem outros fatores além da "profundidade" que contribuem para "quanto tempo leva para fazer o cálculo". Por exemplo, o fio mais longo de um circuito geralmente é um gargalo na computação VLSI real, pois sua capacitância maior leva mais tempo para carregar.