What is Algorithmic Efficiency?

  • A way to find the fastest and least resource dependent solution to a problem
  • Measures using number of computations (you can think of them as steps) in a algorithm before you can solve your problem
  • Generally speaking less computations = faster = better code but it’s heavily dependent on input size as algorithms with small input sizes may sometimes seem faster but are actually much slower at high input sizes

Basic Algorithm Example:

  • Picture a set of 4 cards numbered [4,6,7,2]. To sort these cards algorithmically, you run through them from left to right, comparing if the numbers are bigger or smaller than the card to their right.
  • If they’re already ordered correctly, you keep them as is and mark down that you made a comparison. If they’re bigger than the card on their right, you swap their positions and repeat the process for the next set of 2 cards, until you fixed them entirely. You mark down comparisons and swaps throughout the algorithm.
  • For this example, you have to make 7 comparisons and 3 swaps to make the list ordered, into [2,4,6,7], even though you’re only actually changing the position of one number.

Better Algorithm Example:

  • A different algorithm for the same problem, for example, one where you instead hold onto the smallest card instead each time you go through the set, could only use 6 comparisons and 1 swap, making it algorithmically more efficient.

Algorithm Efficiency Simply Explained:

  • On the most basic level, you can think of efficiency as a measure of the number of steps it takes you to reach your answer. If one algorithm has 7 total steps and a different one for the same problem has 20, your first algorithm is likely more efficient.
  • But, when analyzing algorithm efficiency, you can only achieve accuracy by measuring with different input sizes as well. This is due to the fact that some algorithms increase their number of steps with polynomial efficiency (linear increasing or other polynomial styles), but others increase exponentially or factorially.
  • Algorithms are only reasonable if their operate with polynomial efficiency

Popcorn Hack 1

Which algorithm in this set is unreasonable and why?

ANSWER : A as it is the only one that increases exponentially (4^x vs x^3, 7+4x, etc.)