O- notation

To indicate the asymptotic high end is O-notation. For a

given function g(n) and indicate by O(g(n)).

O(g(n)) = {f(n): there

exist positive constants t and n0 such that 0 ? f(n) ? t *g(n) for

all n ? n0 }

?-

notation

To indicate the asymptotic low end

is ?-notation. For

a given function g(n) and indicate by ?(g(n)).

?(g(n)) =

{f(n): there exist positive constants t and n0 such that 0 ? t *g(n)

? f(n) for all n ? n0 }

?-notation

To indicate asymptotic tight bound

is ?-notation. For a given function g(n) and

indicate by ?(g(n)).

?(g(n))

= {f(n): there exist positive constants t1,

t2 and n0 such that 0 ? t1 *g(n) ? f(n) ) ? t2

*g(n) for all n > n0 }

The all above scenario shown

in fig.

Fig. Time Complexity notations

During analyzing an

algorithm, mostly consider O-notation because it will give us the high end of execution

time. This is the worst case of execution time.

To

compute O-notation lower order terms need to ignore. Because lower order terms

are relatively insignificant for large input.

Let f(N) = 2 * N2 + 3 * N +5

O(f(N)) = O (2 * N2 + 3 * N +5) = O(N2)

Let us consider the scenario.

cnt =0

for edges node.edges

cnt++

if

edge not in resolved

dep_resolve(edge,

resolved)

resolved.append(node)

Lets observe cnt++ execute count.

When node length is 0, it will execute count 0.

When node length is 1, it will execute count 1.

When node length is 2, it will execute count 2.

Total number of

execution count cnt++ is 0 + 1 + 2 +… + (N-1) = N*(N-1) / 2. So Time complexity

will be O(N2).

The below table helps

to user understand the growth of several common time complexity. Thus help to

user judge if the algorithm is fast enough to get an acceptance.

Length of Input (N)

Worst Accepted Algorithm

?10..11?10..11

O(N!),O(N6)O(N!),O(N6)

?15..18?15..18

O(2N?N2)O(2N?N2)

?18..22?18..22

O(2N?N)O(2N?N)

?100?100

O(N4)O(N4)

?400?400

O(N3)O(N3)

?2K?2K

O(N2?logN)O(N2?logN)

?10K?10K

O(N2)O(N2)

?1M?1M

O(N?logN)O(N?logN)

?100M?100M

O(N),O(logN),O(1)

Table.

Several Common Time Complexity