Q:

Does JVM collection times increase exponentially with JVM RAM size?

I heard an associate say:

JVM garbage collection times increase exponentially with JVM size. This is because the tree of references is a function of the amount of the amount of objects to allocate - and gets exponentially harder to traverse the tree as the number of objects get bigger. 

This sounded right. 
I heard another associate say:

JVM garbage collection on the same machine is linear. Given an 8GB JVM split in two 4G JVMs on the same machine (via microservices) will have the same garbage collection durations because the same OS is slowing you down for the same number of objects. 

This didn't seem right - as the trees of objects on the two smaller JVMs should be shallower and easier to traverse. 
My question is: Does JVM collection times increase exponentially with JVM RAM size?
Assumption: Oracle JVM used. 

A:

While Holgers explanation is correct I would like to put a slightly different aspect to it.
The time a GC takes is directly proportional to the number of live objects in the live set. This is easily demonstrated. Assume that we have two applications with heaps of the same size. In the first heap we allocate 10 objects of 100 MB each and in the second 10 million of 100 bytes each. At the next gc half of the objects in each application are unreachable (dead) and can be collected. 
It is self-evident that it will take longer to trace the graph with the most objects.
(As an aside, I remember reading a measurement of the 'shallow and wide' vs 'deep and narrow' and that there was no perceptible difference but I can't remember where. @Holger: if you have a source I would love to read it)

Note that following established java coding practices will in fact ensure that the live set is small. The JVM expects you to code that way and goes to pretty great lengths to help keeping the live set small, escape analysis being just one trick up Hot Spots sleeve. 

So, in short: NO

