-1

What programming language along with implementation and compiler can I use to study the pure, unoptimized space complexity of an arbitrary algorithm? And what methods can I use to do so?

For example, Scheme and Elixir implement tail call optimization. If the algorithm I wrote were recursive, whatever methods I could use to get at the stack might show O(1) space complexity.

Another example, NodeJS implements garbage collection. For any data structures I initialize in my algorithm, I won't know if they are allocated on the stack or the heap so calling the process.memoryUsage() method won't allow me to benchmark consistently.

If I can select an environment to analyze the baseline space complexity of an algorithm, I can then compare it to other environments and thus choose the right tool for the job.

0

Programming languages and implementations do not exist in a vacuum. They are the product of various optimizations that could be applied at any time without you even knowing it, and if they aren't, then you're dealing with a naïve language and implementation and their performance will be less than optimal anyway.

In other words, the fact that Scheme uses Tail Call Optimization is a feature, not a bug. You have to account for that as part of your space complexity. If you want to know what that looks like without TCO, then you either have to defeat it (by making the recursive call not a tail call), or use your own stack instead of the language's.

For memory usage, I suggest that you simply count the number of objects that your algorithm uses, rather than trying to get raw memory usage from the operating system.

Don't forget that Big O can be calculated without ever running your program.

  • I recognize your point about language features and your point that Big O can be determined without knowing the exact units, such as milliseconds for time and bytes for space. However, assume I am an empirical learner. Is there a language out there with features that expose the amount of memory a recursive instruction on the stack takes or an object or primitive takes on the stack or heap? So that I could see the Big O happening with actual units and numbers. – Ryan Jarvis Oct 16 '16 at 21:38
0

The best environment is probably paper and pencil.

That put aside, if you're looking for tool to demonstrate different behaviour on real-world hardware (but in synthetic, i.e. non-optimized etc. environment), i.e. academic, go for something that's

  • flexible enough to allow all your experiments
  • easy enough to program (i.e. support for higher level concepts)
  • gives control over optimisation at compile/runtime
  • keeps measurement clean, i.e. doesn't come with unpredictable overhead
  • provides features to measure memory/time usage

In my book, C++ fits the bill. Obviously very versatile, it also has many libraries available that support your experiments (don't bother implementing vector or hashtable yourself). And most compilers will let you go with (almost?) zero optimisation.

If you're looking at Java, for example, it may be easier to write the code, but the level of optimisation cannot be controlled. Add garbage collection at random times, JIT compilation etc, and you realise that you need to be look very careful when interpreting the measurements.

If doing this for practical reasons, do it on the platform that actually matters. There's no point in proving an algorithm works in C++ on a Windows machine while your JavaScript library just fails on a mobile phone running some specific browser.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.