For a tree of height h and branching factor b, the total number of playout steps of a NS of level n will be \(t_n(h, b) = t_n(h-1,b) + b \times t_{n-1}(h-1,b)\) . The total number of playout steps of a LDS of level n will be \(t_n(h, b) = t_{n}(h-1,b) + (b - 1) \times t_{n-1}(h-1,b)\) . The difference between the complexity of two searches is \(t_{n-1}(h-1,b)\) . The complexity of a NS of level n is O(\(b^n \times h^{n+1}\) ) [1]}. So \(t_{n-1}(h-1,b)\)  is small compared to \(t_n(h-1, b)\)  and therefore NS and LDS have similar complexities even if LDS can be slightly faster. However if the complexity is also related to a better move ordering such as in decision problems, NS with high levels can become faster than LDS with high levels since NS spends much more resources on the choice of the move to search more.
