Understanding Complexity: The Role of Space, Time, and Entropy

I believe many inexperienced programmers misunderstand complexity. It's like a triangle with three sides, and your choice of data structures and algorithms determines how growth occurs along these edges. These edges represent independent concepts in theory, but they are connected by the choices we make.

Why do we need another edge for Randomness, or Entropy? When solutions admit two configurations, there are two ways to encode them, indicating which specific configuration was used. Maximum complexity occurs where most other representations must be excluded; this exclusion affects whether time or space is more impacted.

ELI5. Alright! Let's break this down into simple terms:

Imagine you're playing with building blocks. The way you build something can be like an "algorithm," or a set of instructions.

1. Space (Memory Required): Think of space as how many blocks you need to keep in your room. If you have more blocks, you need more space to store them.

2. Time (Computation Duration): Time is like how long it takes you to build something with those blocks. The longer it takes, the more time you spend building.

3. Entropy (Space of Configurations): Entropy is a fancy word for all the different ways you can arrange your blocks. If you have lots of different ways to put them together, that's high entropy. But if there’s only one way or many ways without much difference, it's low entropy.

• When space and time increase, it's like needing more room in your room (space) and spending more time building (time). They grow steadily as you add more blocks.

• Entropy is highest when you have lots of different ways to arrange the blocks but not too many or too few. It’s like having just enough options to be creative without getting overwhelmed.

4. Solutions with One Configuration: If there's only one way to build something, it's like following a single set of instructions that always works the same way every time.

5. Solutions with Two Configurations: When you can build in two different ways, it’s like having two sets of instructions. You need to know which one you're using, just like choosing between building a tower or a bridge!

So, algorithms are like rules for playing with blocks, and they depend on how many blocks you have (space), how long it takes to play (time), and the different ways you can arrange them (entropy).

---

For binary decision data types, the peak complexity is log2(N), representing the number of comparisons needed for specific operations like insertions in ordered lists, binary trees, or the limit case of hash tables with maximum collisions (where N depends on the data structure or algorithm to manage individual slots).

The Donoh-Tanner phase transition theorem links combinatorial geometry and high-dimensional polytopes, affecting representation complexity. Regular polytopes exist in dimensions greater than two; Donoh-Tanner's result suggests that a k-dimensional object can be reconstructed from k log(N) points in an N-dimensional space. The balance between vertices aligning and solving linear systems via Gaussian elimination leads to average and upper bound results as per Donoh and Tanner.

ELI5. Alright! Let's break this down into simple terms:

1. Maximum Complexity: Imagine you have a big box full of different toys, but you can only play with one toy at a time. If there are lots of toys to choose from, it gets really tricky to decide which one to pick. This is like when something has "maximum complexity" – it's very complicated because many options need to be left out.

2. Time or Space: Think about having two big jars: one for cookies and one for candies. If you have more space in the cookie jar, you can store lots of cookies but fewer candies. The tricky part is deciding which jar (time or space) gets bigger when something complicated happens.

3. Donoh-Tanner Phase Transition Theorem: This is like a special rule that connects two different kinds of puzzles – one with shapes and another with many-sided figures in a big, imaginary world. It helps us understand how tricky these puzzles can be.

4. Binary Decision Data Types: Imagine you have a list of your favorite animals, and you want to add a new animal but keep the list in order (like alphabetically). The "peak complexity" is like figuring out how many steps it takes to find where the new animal goes. For binary decisions, this number is related to how big the list is – kind of like counting how many times you can split your toys into two groups until there's only one toy left in each group.

So, all these ideas are about understanding how complicated things can get when we have lots of choices or need to organize information.