In Progress
Lesson 4, Topic 2
In Progress

# Time Complexity

Lesson Progress
0% Complete

The time complexity of an algorithm is the amount of computer time it needs to run to completion.

The time T(P) taken by a program P is the sum of the compile time and the run (or execution) time. The compile time does not depend on the instance characteristics. Also, we may assume that a compiled program will be run several times without recompilation.Consequently,we concern ourselves with just the run time of a program. This run time is denoted by tp (instance characteristics).

Because many of the factors tp depends on are not known at the time a program is conceived,it is reasonable to attempt only to estimate tp. If we knew the characteristics of the compiler to be used,we could proceed to determine the number of additions, subtractions, multiplications, divisions, compares, loads, stores, and soon, that would be made by the code for P. So,we could obtain an expression for tp(n) of the form:

where n denotes the instance characteristics, and ca, cs, cm, q, and soon, respectively, denote the time needed for an addition,subtraction, multiplication, division, and soon, and ADD, SUB, MUL, DIV, and so on, are functions whose values are the numbers of additions, subtractions, multiplications, divisions,and soon, that are performed when the code for P is used on an instance with characteristic n.

We can determine the number of steps needed by a program to solve a particular problem instance in one of two ways. In the first method,we introduce a new variable,count, into the program.This is a global variable with initial value 0. Statements to increment count by the appropriate amount are introduced into the program. This is done so that each time a statement in the original program is executed,count is incremented by the step count of that statement.

Ex 1: When the statements to increment count are introduced into Algorithm 2, the result is Algorithm 4. The change in the value of count by the time this program terminates is the number of steps executed by Algorithm 2.

Since we are interested in determining only the change in the value of count, Algorithm 4 may be simplified to Algorithm 5. For every initial value of count, Algorithms 4 and 5 compute the same final value for count. It is easy to see that in the for loop, the value of count will increase by a total of 2n. If count is zero to start with, then it will be 2n + 3 on termination. So each invocation of Sum (Algorithm 2) executes a total of 2n + 3 step.