A road named NoNameUno

I must say that I've seen way too many smart software engineers with lack of understanding in Algorithmic complexity. Not sure if they did not have a basic course or just slept through those classes since they hardly contribute to hack some code to working conditions. So a good basic knowledge of it is perhaps helpful.

 So what is this Algorithmic complexity anyway?

Well, consider a simple program first. Now in a structured programming language, one would code with some of the following constructs -

• loops - for loop, while, do while  etc.
• conditional statements - if then else and its variant
• sequential flat statements - Initialization, Allocation of memory etc.
• api calls to systems -  malloc, strcpy  etc.
• Finally composition of functions to form the program - main(), foo(0, bar() etc.

 In a loop, there could be function calls, and other statements. If it is a function call, find the complexity of a function and replace it there. If it is a statement then find the complexity of the statement. Since finding the complexity of a function really boils down to finding the complexity of the statements it used, knowing complexity of different statements is all that is needed here.

 Now any initialization of a scalar variable takes constant time, say k unit of time. Unit of time is unnecessary to define at this stage, since the idea is to analyze the complexity and compare with other algorithms that solves the same problem. Any vector variable, for example an array initialization takes  n * k unit of time, where n is the size of the array.  In complexity analysis term, constant time is defined as  O(1), and n * k is defined as O(n), where n is the size of the array.

Conditional statement's complexity is defined to be the maximum complexity of all the branches. So in a simple if then else statement, if the if block has complexity of O(n), and else has complexity of O(1), then the whole conditional statement has complexity of O(n).

Loop complexity is defined to be the multiplication of the loops bound with the maximum complexity of all the statements inside the loop. If the loop runs thru a list or array of single dimension of size n, the loops bound is O(n). Now if the maximum complexity of all the statements inside the loop is O(n), then the whole loop has complexity = O(n) * O(n) = O(n^2). 

But remember that loop using while or do while is little tricky, since the condition that drives the loop could turn out to be evaluated as false on different situations, so worst case complexity is what we need to take. By the way, all these analysis are for worst case complexity, and it is the upper bound analysis. So we using Big-O here. Usually finding minimum complexity is quite harder. For lot of algorithms, minimum complexity is unknown. 

 After analyzing all the components, you will come up with a polynomial of the form -

O(n^k) + O(n^k-1) + ... O(n^2) + O(n) + O(1).

More over some algorithm can have complexity like O(log n), O (log log n) etc. These terms could also belongto the above stated  general form of polynomial complexity.

This is where comes the polynomial complexity, the P space, NP space etc. NP space is defined in a little different way. When we try to solve some problem and see that there is no fixed k for which we can have the complexity of the above form, we know it does not seem like it has an algorithm of polynomial complexity. For example, some algorithm has exponential complexity. When this happens, we say that the problem is NP hard. Graph algorithms and other optimization problems often sees this type of hard problems. See some algorithm book for more detail.

When someone finds a problem that is NP hard, the next step is to reduce a known NP complete problem to this new problem using a polynomial time algorithm. If the reduction is mathematically correct, the new problem belong to the NP-complete class. What it tells is that if any of the problem in the NP complete class has a polynomial time solution, then the whole class have polynomial time solutions, hence the whole class of NP complete problems have Polynomial complexity.  This is a real hard problem to show any of these problems in the NP complete set has polynomial complexity. Also it is quite hard to come up with a polynomial time reduction of a know NP complete problem to NP hard problems. For lot of problems, finding such a reduction is no small feat. And that is why we see lot of problems are NP hard, and some of the brightest people could not find a polynomial time reduction yet.

So in summary, most of the complexity analysis is really for worst case scenarios. Hence upper bound analysis. Finding lower bound of an algorithm is bit difficult. For example, sorting by comparison has Omega(n log(n) ). But for lot of algorithms there is known lower bound. And when a problem is classified to be NP-hard or NP-complete, alternative options like: Problem domain restrictions; Heuristics and Approximation; Probabilistic algorithms are alternative approach to find good enough solutions. For example, lot of graph algorithmic problems are either NP-hard or NP-complete. But restricting the domain of those graphs, specially for recursively definable graphs, linear solutions can be found. Note here that when we say recursively definable, it restrict the domain of all possible graphs.

That's it about Computational complexity analysis.