The Charm of Computational Theory and Algorithm Design: Part 1 of 2

There is an eternal charm about designing the most elegant and efficient algorithm to solve a given problem, even in these days when enormous computational resources are available through gigahertz processors, massively parallel compute engines, broadband networks and terabyte storages. It’s like the fact that the lead singer’s voice is still the primary attraction in a music album even with the greatest of technological advances in orchestra, acoustics and recording studio.

In computational theory, the key metric of an algorithm’s goodness is its computational time complexity. It measures how the run time of the algorithm varies with the problem size. Can it handle problem instances of larger and larger sizes? It’s always such an important question and especially so in the present times of data explosion coupled with the mindset of the users to get instant responses from software applications they interact with. The problem size is usually denoted by ‘n’ and the computational time complexity of the algorithm is expressed as a ‘Function of n’.

In this two-part article, let’s see examples of computational time complexity growth and how the entire stack builds up. The picture shown will serve as a useful reference for the descriptions that follow.

Sometimes we are surprised that an application runs quite fast even when presented with a large data set, while some other application seems to take forever even on a smaller amount of data. Why does that happen? The insight into the algorithm’s time complexity through the following illustrations will help to get a better understanding to this question.

1. Constant Time Algorithm, C

In practice, there are only a few useful problems that can be solved by algorithms running in constant time. This means the algorithm’s run time does not have any dependency on the size of the input data. Here is one such example.

Consider an electronic bidding system where ‘n’ denotes the number of users making the bid. As the users enter a bid, their information is stored successively in an array data structure.

If the problem were to be defined as selecting the user who makes the first bid, then we can easily see that the algorithm can work without any dependency on ‘n’, the number of users. It merely needs to refer to the first element in the array to select the “first bidder”.

The time complexity of this algorithm is said to be a constant, ‘C’. It does not matter how many users made the bid. The first one to make the bid is the one to be selected.

2. Linear Time Algorithm, O(n)

Continuing with the same scenario as above, let the problem be defined as selecting the user who has made the highest bid, after all the n bids have been received.

This problem will require an algorithm that checks all the n bids to select the highest bid. In other words, there will need to be n computational steps of simple comparison of values. This algorithm will take a run time that is “of the order of n”, denoted as O(n), Linear Time.

It’s to be noted that the underlying speed of the compute machine is not relevant in this representation of time complexity. O(n) means if the algorithm would take a time of X for running on an input of say, thousand users, it would take a time of 1000X for running on an input of one million users. X itself can be just a millisecond or microsecond depending on the speed of the underlying compute machine.

3. Quadratic Time Algorithm, O(n-power-2)

Let’s extend the problem above to select the “top k” highest bidders, instead of only THE highest bidder. In a simplistic design of the algorithm, the same method in algorithm (2) can be extended k times. The first step of selecting the highest bidder will take n computational steps, the second highest bidder will take (n-1), third (n-2), and so on.

Total time required to find the Top k bidders = Sum of expression (n-i+1) for i ranging from 1 to k.

The above expression will be of the order of n (Linear Time) for small values of k, but as the value of k approaches certain significant fraction of n, the time will become a quadratic function of n (Quadratic Time). For example, when k = n/2 (i.e. selecting the top 50% of highest bidders), the number of computation steps will be n/4*(n + n/2 + 1) for even numbers of n. That is, the algorithm will require a run time of the order of n-power-2, denoted as O(n-power-2).This algorithm is not efficient for higher values of k and can be improved to become optimal, as illustrated in the next section.

4. Time Complexity Involving Logarithmic Function

Continuing from (3), for higher values of k, we can design a much better algorithm by firstly sorting all the bids received in the descending order of the bid value. Then selecting the top k bidders would simply require selecting the first k entries in the sorted array. Well known and efficient sorting algorithms are available which have computational time complexity of O(n*logn), where the logarithm is to the base of two. Hence the overall time complexity of finding the top k bidders is bound by the same order of O(n*logn). It is to be noted that the logarithmic function of n grows much, much slowly with n, which means the algorithm would be highly efficient in run time.

As a variation in this example, if the problem were to just determine if a bid of a specific value has been made by any of the users, binary search can be made on the sorted array to yield the answer in less than or equal to logarithmic time. That would be of just logarithmic time complexity, O(logn).

5. Polynomial Time Algorithms, O(n-power-k) and Class of P

In general, any algorithm whose computational time complexity can be expressed as a polynomial function of n, where a constant k is the degree of the polynomial (value of the highest power of n) is called a polynomial time algorithm of time complexity O(n-power-k).

The Class of P denotes all computational problems which can be solved by polynomial time algorithms. This includes constant time, sub-linear and logarithmic time algorithms.

Big Shift from Polynomial Time to Non Polynomial Time Algorithms

As we would expect, for practical usage in software applications, an algorithm needs to have polynomial time complexity, that too of a very small degree. We can visualize how the run time would explode for even a degree of 2, when the input size grows from thousands to millions.

However, the world of computational problems is not limited to only polynomial time algorithms. Specifically, there exists a class of problems called NP (Nondeterministic Polynomial) for which known algorithms guaranteed to provide optimal solutions require exponential run times, such as, 2-power-n or n! (Factorial of n). Such algorithms cannot be implemented as such in large software applications as the run time would extend to several tens of years, if at all they would ever finish running!

The Class of NP is intriguing. It contains several important problems with major real-life applications in cryptography, social graph, VLSI design, drug discovery, network design, etc. So, NP can’t be ignored. The inherent challenge in NP arises due to the combinatorial explosion of the solution space which needs to be searched to determine the optimal solution. In simple terms, there are billions of points to be searched to find the optimal solution which is impractical or one can search a smaller space (in practical run times) by compromising to an extent on solution accuracy. Do we have any hope of finding the optimal solution in polynomial time for NP Class problems?

The question “is P = NP?” (“P vs NP problem”) is one of the principal unresolved problems in Computer Science. It’s widely believed that P is not equal to NP. Research efforts continue to be invested around the world to answer this question either way, without any success so far.

It’s interesting to note that in some cases, a slight variation in a problem definition can shift it from P to NP Class! For example, finding the shortest route on a map from location A to location B can be done in O(n-power-2) run time using E W Dijkstra’s famous shortest path algorithm. However, if the problem is re-defined as finding the shortest route from location A to location B, while also visiting every other location exactly once, it moves to NP Class since there are exponential number of combinations in which the n locations can be ordered to form the overall route. More on this in Part II of this article.

It’s now time for a little break. In the second and concluding part of this article, we will look into understanding the Class of NP, completing the overview of the Computational Time Complexity Stack and a few design considerations for algorithms.