Thinking about algorithms - P1

This is a random thought that occurred to me during my walk. There is a vast amount of knowledge available about algorithms and data structures on the web, which will surely answer any particular asks that you may have. During an evening stroll, I started wondering different ways of thinking about algorithms. And this is one of those skewed ideas. Here we go..

Imagination

Imagine we have a square piece of land which we are going to use for storage. And we will receive 'n' number of boxes that we will need to store in this piece of land. Lets figure different ways in which we can store the received boxes. We will define how we want to store the boxes in the space and then contemplate pros and cons of our solution. (We will stop with two solutions since there can be as many as we can imagine - will leave the rest for your brains to think through and imagine)

Lazy!

• As we receive a box, we can place it in the space we have where ever possible.
  • a box can be placed on an empty land
  • a box on top of another box

Pros:

• Faster placement: Don't have to think about where to place the box. We only need to find an available slot and place the box on it.

Cons:

• Space loss: Since we are randomly placing boxes, there will be a situation where we wont effectively use all available space.
  • We will reach a storage threshold quicker due to loss of storage space.
• High cost of retrieval: If there is a need to retrieve a certain box - its a needle in haystack problem. Rather not search for the box!
  • The time and cost required to retrieve a box increases with the increase in number of boxes we store.

Indexed/Catalogued

Learning from our Lazy solution limitations, we come up with the next iteration of storage solution.

• We shall allot a number to each box as we receive them and then place them in the slots on the land which we will number as well.
  • This will give us ability to know where certain box is located
• Instead of placing the boxes in random available slots, we will place them next to each other until the whole land is covered.
• Once the land is all filled up, we can then repeat the above process but by placing the boxes on the first layer of boxes.
  • We are well organized now.. Yay

Pros:

• Effective use of all space available
• Ability to retrieve a box because they are indexed/labelled

Cons:

• Comparatively higher cost to place a box in its place
  • Since we need to label, find the next empty slot and place the box there

Think - Cost and Time:

Visualize the above two solutions and think of the following parameters:

• Cost of storage/retrieval
• Time take to store/retrieve

If you think about it carefully, its hard/impossible to come up with specific numbers for the cost and time involved. Because, they will vary based on a multitude of other factors.

• Do we use machinery/automation
• Can multiple boxes be accepted and placed at the same time

Similar is the case with programs as well. It depends on the hardware or network performance and capability. As such, Big-O and standard notations always speak of relative space/time complexities and not absolute numbers.

The above are what we also try to calculate for computer algorithms. Cost and time to store, retrieve, sort, remove, search etc.. We will probably explore these mathematical derivations and notations in a follow up post.