I am trying to find a very rough Big O bound on the following summation: $$\sum_{x=2}^{\lg\lg N}\sum_{j=1}^{2^{2^x - 1}} 1 = \sum_{x=2}^{\lg\lg N} 2^{2^x - 1}$$
I am not exactly sure what format function would bound the summation of the above. I am thinking that $2^{2^x}$ could be bounded by $2^{n!}$ but regardless, I am not sure how that would work out in the summation. Any ideas as to how to upper bound this?
Note that $$ \sum_{x=2}^m 2^{2^x} \le \sum_{y=2^2}^{2^m} 2^y = O\left(2^{2^m}\right). $$ The first ≤ can be seen by checking the number of terms of each side. The second = is because of geometric series. Put back $m = \lg\lg N$ to get the upper bound being $O(N)$.
It can easily be shown that a lower bound is $\Omega(N)$ by keeping only the last term of the summation. Thus the asymptotic tight bound is $\Theta(N)$.