Time complexity of memory allocation

by

One of the things you have to realise when dealing with O notation is that it is often very important to understand what n is. If the n is something related to something you can control (eg: the number of elements in a list you want sorted) then it makes sense to look hard at it.

In most heap implementations, your n is the number of contiguous chunks of memory the manager is handling. This is decidedly not something typically under client control. The only n the client really has control over is the size of the chunk of memory she wants. Often this bears no relation to the amount of time the allocator takes. A large n could be as quickly allocated as a small n, or it might take much longer, or it might even be unservicable. All this could change for the same n depending on how previous allocations and deallocations from other clients came in. So really, unless you are implementing a heap, then the proper answer is that it is non-deterministic.

This is why hard realtime programmers try to avoid dynamic allocation (after startup).

More Related Contents:

  1. Memory Allocation/Deallocation Bottleneck?
  2. convert malloc to new c++ for struct
  3. How to improve performance of this code?
  4. When is optimisation premature?
  5. How do malloc() and free() work?
  6. What Every Programmer Should Know About Memory?
  7. What do the terms “CPU bound” and “I/O bound” mean?
  8. SIMD instructions lowering CPU frequency
  9. How much of ‘What Every Programmer Should Know About Memory’ is still valid?
  10. How to dynamically allocate memory space for a string and get that string from user?
  11. How can I rank observations in-group faster?
  12. Deflate compression browser compatibility and advantages over GZIP
  13. What is the difference between “new” and “malloc” and “calloc” in C++? [duplicate]
  14. Is the inequality operator faster than the equality operator?
  15. RDTSCP in NASM always returns the same value (timing a single instruction)
  16. foldl is tail recursive, so how come foldr runs faster than foldl?
  17. How to find the cause of a malloc “double free” error?
  18. Explain this implementation of malloc from the K&R book
  19. What’s the fastest way to divide an integer by 3?
  20. What is Big O notation? Do you use it? [duplicate]
  21. How do I free memory in C?
  22. Why do you specify the size when using malloc in C?
  23. Can I use the “null pointer optimization” for my own non-pointer types?
  24. Logger slf4j advantages of formatting with {} instead of string concatenation
  25. C: Correctly freeing memory of a multi-dimensional array
  26. dynamically allocated memory after program termination
  27. What happens if I try to access memory beyond a malloc()’d region?
  28. When do programmers use Empty Base Optimization (EBO)
  29. Why exactly should I not call free() on variables not allocated by malloc()?
  30. Fastest way to loop through a 2d array?

Leave a Comment