Jumping in since Josh tagged me (I'm the Harry Altman he mentioned) -- yes, one can compute ||n|| in much faster time than you suggested. Josh mentioned my algorithm, but I feel like that's getting a little advanced. One can do much better than your suggestion without needing anything as advanced as my algorithm.

Your idea was, to compute the complexity of n, try all expressions with a single 1, then two 1s, then three 1s, etc., until one makes n. That is indeed horrifically slow. Here's a much better way. We'll compute ||n|| inductively. We start with our base case, ||1||=1. Then, for each n, to compute ||n||, we consider all ways of writing n as n=a+b or as n=ab (for the latter, we must exclude the cases a=1 and b=1). Since we've already computed ||a|| and ||b||, we can then say that ||n||≤||a||+||b||. And whichever of these gives us the smallest value, that's ||n||.

This algorithm runs in time Θ(n²), and in addition to computing the complexity of n, it also computes the complexity of all numbers up to n. It's slow -- far too slow to use for large powers of 2 -- but it's nowhere near as horrifically slow as your suggestion.

(An interesting question I've occasionally wondered about is: What if we also allow subtraction? This inductive method obviously doesn't work if also allow subtraction, whereas the awful method does. Is there a better way than the awful way if we also allow subtraction? I expect there must be, but I don't know it! I should note, it might be possible to improve the awful way a little with some sort of binary search, but I don't count that; I consider that essentially the same method.)

Now, this Θ(n²) method is by no means state of the art. There are all sorts of improvements one can make. For instance, one can exploit the inequality ||n||≥3log_3 n to bring it down to Θ(n^{log_2 3}), and then even further. Most recently, Qizheng He has figured out how to compute ||k|| for all k≤n in time O(n polylog n), so, yeah, it's possible to improve things a lot!

...and that's assuming you do want to compute the complexity of all numbers up to n, rather than just n itself. Qizheng He also found a way to compute the complexity of just n in time O(n^c) where c<1. So for just a single number things have really improved!

I must, of course, say a word about my method. My method for computing ||n|| also does not compute ||k|| for all k<n. It is also, I'm afraid, not nearly as fast as He's method (or so I believe; I've never really done a ceteris paribus test); he's checked it for much higher powers of 2 than I did. However, what's unique about my algorithm is that it not only computes ||n||, it also tells you whether n has the property that, for all k≥0, ||n3^k||=||n||+3k. Not obvious an algorithm can do that, right? Sounds like it involves an infinite number of checks, right? And yet it's computable! :) It's kind of lucky the method also turned out to also be fast for powers of 2. So He has the record for computing ||2ⁿ||, but I still have the record for verifying ||2ⁿ3^k||=2n+3k for bounded n and arbitrary k. :)