Programming complexity

This is an old revision of this page, as edited by 220.237.41.195 (talk) at 14:23, 14 September 2007 (Big O complexity, java examples, general description). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The complexity of most computer programs and programming languages is one of the unsolved problems in software engineering. The current applications are complex to the extent that when programmers leave, companies fail, if those companies have no one else who understands what the programmers have done. Researchers have performed a great deal of research in an attempt to develop metrics, which adequately capture the complexity and reduce complexity of the software.

In general terms the complexity of a program is the number of steps that it takes to solve a problem or solve an algorithm. A smaller complexity means less steps and a more efficient program. Efficiency is of dire importance to every Computer Scientist and Software Engineer - these professionals are often coding Millions of methods in the one program, imagine if they all had large Complexities!


Big O Notation

In Java complexity is often notated using Big O notation. It is formal coding procedure to precede all methods with commenting that describes their precondition, postcondition and best/worst complexity. For Example:

/*square method

  • preCondition: none new
  • postCondition: the square of the passed integer is returned
  • complexity: best case O(1) worst case O(1)
  • /

public static int square(int number) { return number*number; }

The notation O(1) mentioned above means that the program is Constant or Linear. For a program to be O(1) it must not have a for or while loop which depends on the number of elements in an Array, Link or other data structure.

When we are iterating through an array or other list we say that the number of elements in the array is N. If we have an unbreakable for or while loop the complexity will always be O(N) or greater. If the for loop breaks at any point the complexity can change, for example:

/*search method

  • ...
  • complexity: best case O(1) -Item being searched for found first- worst case O(N)
  • /

public static boolean search(int number, int[] theArray) { for(int i =0; i<theArray.length; i++) { if(theArray[i]==number) { return true; } } return false; }

If a for loop is embedded inside a for loop the complexity is O(N)*O(N) or O(N2). This also works for calls to other methods. Ie, if in our search class during the for loop we called on the square method mentioned above something like this:

public static boolean search(int number, int[] theArray) { for(int i =0; i<theArray.length; i++) { int anumber = square(number); if(theArray[i]==anumber) { return true; } } return false; }

the complexity would be O(N)*the complexity of square(). Or O(N)*O(1) which just ends up being O(N). Where if we had the method fakeSort -

public static boolean fakeSort(int[] array) { for(int i =0; i<array.length; i++) { for(int j =array.length; j>0; j++) { if(array[i]<array[j]) //swap these } } }

the best and worst complexity would be O(N2).

Complexity comes in many forms and this Wiki does not yet cover even half of the details.


See also