Time Complexity -mycodeschool

Time Complexity - why should we care?

n is a prime?

with the increasing of the number n,B is faster than A.

How to analyze Time Complexity?

Input -rate of growth of time

we suggest a model machine:

• single processor

• 32bit

• sequential execution

• 1 unit time for arithmetical and logical operations

• 1 unit for assignment and return

O is an Asymptotic notation(渐进符号)

T_sum = k O(1)

T_sumoflist = Cn + C^| O(n)

T_sumofmatrix = Cn² +C^|n +C^|| O(n²)

Time Complexity analysis - asymptotic notations

O -"big -on" notation -> upper bound

O(g(n))={f(n):there exist constants C and n₀ ,f(n)<=Cg(n),for n>=n₀}

eg:

f(n) = 5n² +2n + 1

g(n) = n² C=5+2+1=8 n₀ = 1

f(n)<=8n² , n>=1

Ω - Omega notation->lower bound

Ω(g(n)) = {f(n):there exist constants C and n₀ Cg(n)<=f(n),for n>=n₀}

eg:

f(n) = 5n² +2n + 1

g(n) = n² C=5 n₀ = 0

5n²<=f(n) , n>=0

θ - Theta notation -Tight bound

θ(g(n)) = {f(n):there exist constants C₁ ,C₂ and n₀ ,C₁g(n)<=f(n)<=C₂g(n),for n>=n₀}

f(n) = 5n² +2n +1

g(n) = n²

C₁ =5 C₂ =8 n₀ =1

5n² <= f(n) <=8n²,n>=1

Time Complexity analysis -some general rules

We analyze time complexity for:

• Very large input-size

• Worst case scenari0

Rule:

• drop lower order terms

• drop constant multiplier

eg:

T(n) = 17n⁴ + 3n³ + 4n +8-> T(n) = n⁴ ->O(n⁴)

Rule:Running Time = the sum of running time of all garments

in a program:

simple statements fragment1 O(1)

signal loop fragment2 O(n)

nested loop fragment3 O(n²)

it takes O(n²)

if we use if fragment2 O(n) else fragment3 O(n²) ,it also takes O(n²)

we always try to analyze it in the worst case

Rule: conditional statements, Pick complexity of condition which is worst case