As you pointed out there is a trade-off with allocating full memory against fast allocation.
Typically we can use a bin analogy to demonstrate speed vs allocated memory. Ultimately the algorithm that allocates all the memory is one that has a region of RAM and allocates every byte to a particular memory handle for a process. Now this is insane because you would need to have other memory to say what process and handle is associated with each byte and all of that overhead would be ridiculous.
So the next thing to do is to say that we have so many bins and these bins hold all of the memory for a process. You might have more than one bin that is set aside for a process.
Now pretend your pieces of "garbage" (ie the chunks of memory allocated to the process) are to be packed into your bins. This is a well known problem that is called the N-D bin packing problem, where N in this case is 1.
From this you start to get an idea about how to analyze fragmentation.
Now on top of this you have to use domain specific knowledge about memory allocation. Although good programmers will write routines that don't abuse memory allocation where its not needed, there are cases where you will not know in the future how much memory you need.
So essentially you need to take into account not only the bin packing problem, but also the issue that memory will be freed and allocated dynamically and that adds a whole new dimension to your problem.
Thankfully since memory is plentiful (in comparison to the past), we can use fairly large bin sizes and many programs will allocate memory that is far less than the available memory (that is RAM - kernel memory - other allocated memory).
Also in the above case, you have enough bins that if a small chunk of memory is freed from one bin and a new allocation is bigger than what's available, then due to the amount of memory, you can easily use another bin.