Algorithm Basics: Objective C

Familiarizing with time complexity analysis required to become an efficient programmer. This tutorial focus on giving a very precise introduction to time complexity analysis. Lets get started.

Sorting is a typical example which is taken to explain the concepts of algorithm clearly. We are also going to see the very same sorting problem which every programmer faces in his life.

Lets consider, bubble sort.

This tutorial is not meant to explain bubble sort. But anyways, I will give an overview of the algorithm. The basic idea behind bubble sort is to compare the two adjacent elements and replace the elements accordingly if required. The history behind this sorting algorithm will be dealt in another tutorial.

Algorithm for bubble sort to sort the array in descending order

-(NSArray*) bubbleSort: (NSArray *inputArray) {
    int n = [inputArray count];
    for(int i = 0; i< n; i++ ) { //Outer loop
          for(int j=0; j<n-1; j++) { //Inner loop

               if(array[j] < array[j+1]) {
               int temp = array[j];
               array[j] = array[j+1];
              array[j+1] = array[j];
         }
   }
}

If you look at the above program, the worst case input will be to replace the position of all the elements in the array. The input of such case will be [5, 4, 3, 2, 1, 0].

 For sorting this array, the outer loop will run n times and the inner loop will run n times which bring the complexity O(n^2).

The complexity is defined in terms of the number of instruction cycles executed by the cpu in seconds. The number of instructions executed by the cpu depends on many things such as:  single vs multiple processor, read write speed to memory, 32 bit vs 64 bit operating system, number of input. In algorithms, we will concentrate only on the last option, i.e the input because our aim is to only compare the efficiency of the algorithm irrespective of the platform on which it is running.

Lets take that we are dealing with a single processor which execute the instruction sequentially.

int a =  10;

The above statement takes one instruction cycle. If you dig in to assembly language, the above code will be translated to the following:

.globl main
main:
      movl $10, %ebp

The .globl assembler directive makes the symbol main visible to the linker. This line makes the program linked up with the C start up library. The commands, movl $20, %eax means that the bit pattern of 10 is moved to register %eax.

Example: 1

To find the sum of the two elements.

-(int) sum (int number1, int number2) {
    return number1 + number2;
}

This algorithm take constant time to execute. Its not actually depends on the number of input value. It always required two instruction cycle to do execute this. One to perform the arithmetic operation and another is required by the return statement. So we can say that the time complexity of this algorithm is 2 which is a constant. And in algorithm terms, it is O(1). Always requires a constant time.

Example: 2

Sum of n numbers

double sum = 0;
for (NSNumber * n in numArray) {
  sum += [n doubleValue];
}

It is analogous to 1+2+3+......+n. In this case complexity of algorithm is calculated as number of times addition operation is performed which is O(n).

In general, deeper nesting of for loop will lead to increase in complexity. For example: an algorithm with 2 for loops from 0 to n will result in the complexity O(n^2) and so on.