Running Time Analysis

Here we will do "pen-and-paper" analysis of 4 algorithms (or programs): (i) linear search, (ii) binary search, (iii) bubble sort, and (iv) recursive fibonacci numbers.

Primitive operations.
The basic idea of "pen-and-paper" running time analysis of algorithms or programs is to count the number of primitive operations executed when the program or algorithm is executed. First I'll explain the notion of a primitive operation.

When a program that you write is compiled or interpreted, it is translated into a sequence of simple machine instructions. For example, the Python statement

	x = x + 1

might be translated into:

	MOV x R0	// move the contents of variable x into a special register called R0
	ADD 1 R0	// add the constant 1 to R0
	MOV R0 x	// move the contents of R0 back to x

Here is an example containing an if-statement:

	if(x < y):
		x = x +1
	y = y + 1

This might be translated into:

        MOV x R0
        MOV y R1
	CMP R0 R1	// compute R0-R1
	JNE AFTERIF	// if result is negative, "jump" to instruction labeled AFTERIF
	MOV x R0
	ADD 1 R0
	MOV R0 x
AFTERIF:MOV y R0
	ADD 1 R0
	MOV R0 y

Note that the if-statement itself translated into 4 machine instructions. Here is another example; this time with a for-statement.

	for i in range(1, n+1):
		sum = sum + i
	y = y + 1

might be translated into:

	MOV 1 i
	MOV n R1
	Add 1 R1
LOOP:	MOV i R0	
	CMP R1 R0
	JNZ ENDFOR 	// jump to outside for-loop if (n+1)-i is negative or zero
	
	MOV sum R0	// Body of for-loop
	ADD i R0
	MOV R0 sum

	MOV i R0	// Increment i
	ADD 1 R0
	MOV R0 i

	JMP LOOP	// Go back to start of for-loop
ENDFOR: ...
	...
	...

Each machine instruction takes constant time to execute. What does this mean? This means that the time it takes to execute the machine instruction is independent of the input size. Recall that we are interested in obtaining the running time of the program or algorithm as a function of the input size. Anything that does not depend on the input size is taken to be a constant. This does not mean that the machine instruction will take the same amount of time on different machines or that different machine instructions will take the same amount of time. In fact, how long a machine instruction takes to execute depends on many factors, one of which is the clock speed of the machine. For example, your machine may be running at 2 GHz (gigahertz), and in this case, roughly speaking, 2 billion such instructions can be executed in a second. Slightly older machines may be running at 166 MHz (megahertz) and in this case, 166 million such instructions can be executed in a second. One approach to doing a "pen-and-paper" analysis of a program is to hand translate it into machine code and then basically count the number of machine instructions executed. The problems with this approach are (i) hand translating into machine code is a pain, (ii) we still have to fix a machine instruction set to translate into. This means that the count of number of machine instructions will depend on the hardware platform or compiler and we are interested in avoiding this dependence. Fortunately, this approach is unnecessary and we can take one more step back.

A primitive operation is a high level programming language statement that translates into a constant number of machine instructions. Thus every primitive operation also takes constant amount of time. The same statement in Python may get translated into different number of machine instructions on a different platform or using a different compiler. However, we don't care about the number, we only care about the fact that it is a constant, independent of the input size. As a thumb rule, the following are all primitive operations:

Any arithmetic or boolean expression involving variables or items indexed from an array (list).
An assignment with an expression of the kind described above on the righthand side. items on the right hand side.
Making a function call or returning from a function call.
Flow control statements such as if-statements, for-statements, and while-statements.

Example 1. The expression

	x = C[i] + x - y

is a primitive operation according to the above thumbrule, but it is important to understand exactly why. The only term in the expression that complicates matters a bit is C[i]. The reason why C[i] can be accessed in constant time is that given an index i and the array C the machine can use a simple arithmetic computation to find the address in memory of the item C[i]. There is no search of any sort required to find C[i]. This feature of how arrays are implemented in high level languages is called the the random access property of arrays.

Example 2. The expression

	x = power(m, n) + 1000

is not a primitive operation. Yes, the right hand side is an expression, but the terms on the right hand side are not all variables and there may be a significant cost to evaluating power(m, n).

Linear Search

0.    linearSearch(C, x):
1.	for i in range(0, len(C)):
2.		if(x == C[i]):
3.			return 1
4.	return 0

Suppose that n is len(C). Assume worst case. The for-statement is executed n+1 times, the if-statement is executed n times. The running time is 2n + 1. The constant 1 and the coefficient 2 that you see in this expression are useless. Explain why. So we say the running time is O(n).