Physical complexity. Not informational complexity.
Information is held by something physical. CPU's must have more physical complexity to do more work. Hard drive (or flash, SSD, SAN, NAS, take your pick) become more pysically complex as they hold more information and perform more task.
What is your definition of complexity? Physical complexity refers explicitely to things that are connected and interact. Random distribution would at least imply that there are ~ as many non-connected things as there are connected. More things inter-relating with each other is what "complexity" is regardless of whether we are talking about information or purely physical systems.
I'm very curious what definition of complexity you are using.
Neither a computer or a brain is more complex physically when processing information than when it is not.
Yes, they are. Again, complexity refers to inter-relatedness and connections. By any definition and use case I can come up with, there are more connections and structure when processing information when idle or with no power.