This was the topic of the following discussion a few years ago:

http://cstheory.stackexchange.com/questions/2720/can-the-cost-of-gc-be-neglected-when-analyzing-the-running-time-of-worst-case-da

My personal impression is that the question is not that well-posed:
- if you assume infinite memory, you don't actually need a GC (and for any
input you can tweak the GC setting to make sure no collection happens)
- if you assume finite memory, the notion of asymptotic behaviour breaks
down unless you can prove your algorithm has a finite peak memory
consumption that is below that bound
- this is independent of whether or not your language using a GC; if your
algorithm constantly allocates heap memory, you will run into compaction
issues even with malloc/free that may degrade theoretical performances

Neelk answer in the link I gave above is that if you can tune your GC to
make sure collections happen infrequently enough, you can make collection
amortized constant-time. But that means you have to accept some memory
wasted (the runtime using significantly more memory than the size of the
actually live data), possibly proportional to the running time of your
program.


On Wed, Dec 4, 2013 at 1:20 PM, Tom Ridge
<tom.j.ridge+list@googlemail.com>wrote:

> Dear caml-list,
>
> I have an OCaml program which I expect to run in time O((n^3) *
> (ln(n))) say. My expectations are based (unrealistically) on ignoring
> garbage collection completely. As inputs get large, the program
> performs worse than I expect.
>
> My question is: is it possible for OCaml's garbage collection to alter
> the time complexity of my program?
>
> If the answer is "yes", then are there any expectations I might have
> about how bad this alteration might be? For example, (without thinking
> about it too hard) it seems unreasonable for GC to turn a polytime
> program into an exponential time program, but is this actually true
> for OCaml's garbage collector?
>
> I have read some material on OCaml's GC, but I did not form any
> intuitions yet about the answers to these questions.
>
> Thanks in advance
>
> Tom
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>