In this article I will attempt to explore what can be derived if we assume there are no Computational Limits on Efficiency. However, before we get into that, let's first have a short introduction to what `Computational Efficiency` actually means.

"Efficient programming is programming in a manner that, when the program is executed, uses a low amount of overall resources pertaining to computer hardware. " ~geeksforgeeks

This is unfortunately a weak definition, and fails to cover the picture of what computational efficiency really means. I could not find a better definition online, so I will now attempt to write my own definition of Computational Efficiency:

"Computational Efficiency of an algorithm refers to how well the algorithm succeeds in minimizing the expense of computational resources, and time. An algorithm is considered optimal if no better asymptotic time complexity exists for solving the same problem."

This definition gives a good, concise overview. To aid understanding for those unfamiliar, I will give a couple short examples of what computationally efficient and inefficient problems look like. Assume we have a list of n integers,

it could look like this: x=[1,8,42,3,77,89,44]

and our goal is to find the position of the first occurrence of some given element(assume for this example the element is 44. Now, an inefficient algorithm for this would be to first subtract the number (in our case 44) from all the elements one by one, then again iterate through it searching for the first element with the value 0 in the new list. The time complexity of this would be O(2n) as in the worst case scenario we will need to take 2n iterations (If you remember, n is the length of the list. In our example n=7) to find the location of the element, n iterations to subtract, and n to find the first zero element.

Now, it's very easy to figure out how we can increase the efficiency of our algorithm, i.e reduce the computation required to solve the same problem by decreasing the steps required. Instead of subtracting the target number from each element in our first element, we can (obviously) directly compare each element until we find the target element in the list. This has a worst-case time complexity of O(n) which means that in the worst case we will require n steps to solve the problem given this algorithm.

Huh, that was easy, right? We found an algorithm that...

Posts

Wikitag Contributions

Comments