I have read in many papers that time complexity of WPT is $O(N \log(N))$, but I would like to know what is the effect of Levels in the time complexity.

Must it be one of the following ?

  • $O(2^{L} ~N~ \log(N))$
  • $O(2^{L+1} ~N~ \log(N))$
  • $O(L ~N ~\log(N))$

$ L$ is the number of decomposition levels

Can anyone helps which is true?


1 Answer 1


I just found the answer in a paper. so thought it might be useful for someone.
If we decompose a signal with length of $N$ to $L$ level then time complexity is
$O(L\times Nlog_{2}N)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.