Time vs Memory trade-off in Software

In software, there is always a trade-off in memory and time. You can improve run time of your software at the expense of some extra RAM memory and similarly to improve memory footprint of your software, you may have to compromise with speed of your program. Let us try to understand with a very simple example :

let us say you are implementing a singly linked list, a simple implementation would look like this :

1 2 3 4 5 6 7 8

class Node { int data; Node *next; } class List { node *start; }

If you want to count number of nodes in linked list, how would you do this? very simple, iterate over all nodes :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Node { int data; Node *next; } class List { node *start; public : int size() { int count = 0; Node *temp = start; while(temp) { count++; temp = temp->next; } return count; } }

what is the time complexity? It is O(n) i.e. linear. But imagine if nodes in linked list are in million. Can we reduce run time of this algorithm or can we do it in constant time?

yes, we can. At the expense of very small amount of memory, with 4-8 bytes. How?

instead of counting number of nodes, keep the count in class itself. when you add a new element in the list, increase this count and similarly when you delete an element from list, decrease the count.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Node { int data; Node *next; } class List { node *start; int count; // number of nodes. initialize to 0 void addNode(int value) { Node *node = new Node(value); //add in the front or end count++; } // similarly for deletion }

With just one extra byte of integer, you have reduced run time of algorithm from linear to constant.
This is a very simple and small example. In large software, such simple optimizations can improve run time from days to mins/seconds and at the same time, sometime extra memory required may be too large for significant improvement. So one has to take such decisions very wisely.