Question

How can we measure space/memory efficiency in Java Programming? Is it possible to do so with Big O Notation to an extent? I was told that while the element of speed is important, in some systems you need to be concerned about being lightweight as well (even at the cost of speed). In some embedded systems you might need to severely limit the amount of memory available to a device. How would you approach a solution to that sort of problem?

Answer 1

Firstly it is important to note that there is no such thing as space/memory efficiency in Java Programming or in fact, any programming language. Whenever we talk about space/memory efficiency we talk about the efficiency of algorithms without concern to any specific programming language. Whenever we talk about measuring the efficiency of an algorithm, we talk about its efficiency in two spheres, one: time of execution & second: memory required in execution, we call those 'measures' as time complexity and space complexity respectively. Since, we can have different times of execution & different memory requirements on machines/systems with different hardware and architecture, hence, we measure these complexities using the asymptotic notations. The asymptotic analysis enables us to define an asymptotic complexity class for the given algorithm which again might vary with different inputs for a given algorithm. For example: Quicksort algorithm for sorting a list performs worst for already sorted data with complexity of the order of n² for the input size of n and performs much better for randomly sorted data with complexity of the order of nlogn. This variation causes great variation in the performance of algorithm for inputs of larger sizes. Hence, we measure the worst case time complexity for an algorithm and using that we compare the algorithm with each other. Another important point to be noted is that Big-Oh notation is often mistaken for the worst case time complexity which is NOT the case. Big-Oh defines the upper bound to an algorithm which might be used to define the worst case time but it is an entirely different concept in the sense that it applies to functions for determining their upper bound and not the worst case or best case.

Another important concept is that of the time-space trade off in which decreasing the time complexity leads to increase in the space complexity of an algorithm and vice versa. For systems with severe restrictions on memory to be used, space complexity may be given preference and for the ones with more memory available for execution, time complexity should be given preference. It has been rightly pointed out that memory restrictions may be severe in some programming environments but we can't define any standard for preferring one complexity over another as scenarios tend to be too diverse in nature and real time decisions on the basis of given scenario have to be made. Finally, it all boils down to prioritizing the importance of one over another and thereby deciding which one to minimize at the cost of the other.