# What is Wavelet packet transform (WPT) time complexity

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?

If we decompose a signal with length of $N$ to $L$ level then time complexity is
$O(L\times Nlog_{2}N)$