Week 11: Sorting and Efficiency

Efficiency in general, describes the extent to which time, effort or cost is well used for the intended task or purpose.  – definition from Wikipedia

When we talk about efficiency in Computer Science and programming, we see how much time is needed for a result of the code to be executed; that is usually calculated by how may “lines of code” are ran during the execution.

Ex) Which algorithm is better? - Algorithm A takes n^2– 37 time units or Algorithm B takes n+45 time units, when n presents the input number(or size). OF COURSE algorithm B!

These matter much more when n gets larger, and usually there is not much difference when n is small. Which means efficiency only matters when n is a large number.

Big-O Notation - the time complexity(efficiency) of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and lower order terms (of course since this deals with “efficiency”, we need to think n as a BIG number, as we discussed from the above)

Relationships between orders (for the basic Big-O’s)

O(1) < O(log n)

O(log n) < O(n)

O(n) < O(n log n)

O(n log n) < O(n^2)

O(n^2) < O(n^3)

O(n^x) < O(x^n), for all x and n

Than now, let’s look at sorting…

Many common sorts consists of nested loops (n^2)

Ex) Selection sort, Insertion sort, Bubble sort

Or you can sort recursively by dividing set into two pieces and sorting each piece recursively.

Ex) Merge sort, Quick sort

As we progress in learning in CS, we will be dealing with much more complicated algorithm; without thinking about efficiency, the program that is created will be less helpful and less appealing to the user. What we can see from the above is that there are several approaches to find best algorithm to sort, which means that there is no fixed answer for a problem(usually in real life situation as they are much more complex than just a plain sorting problem). Now our job as a programmer is to come up with new and better algorithm and compare with others to develop with what we already have to make the existing code efficient.