Performance Analysis

Performance Analysis, continued

The model of computation affects complexity

'size' of problem

'basic' instruction = 1 unit

Previous analysis valid of each data item is an atomic entity ie., it can be loaded into one memory location or register and is never broken up.

Algorithm MAXIM
	max   'AA. . .A'
	while (more data items) do 
	        read WORD
		if WORD > MAX then MAX =  WORD
	write MAX

In the worst case n reads, n comparisons, n assignments

T (n) = O(n)

What if WORD contains a large number of characters?
The compiler provides machinery to break up WORD into characters on which basic instructions can execute.

Size of problem depends on number of words and length of word.

| WORD | < m characters
assume character comparison takes 1 unit of time

time for comparisons = n x m
time for assignment = n x m
time for reads = n x m

T (n,m) = O(n*m)

Moral of story: sometimes more than one thing can effect timing, hence more than one variable.

Uniform and logarithmic cost (complexity measures)

Things to consider:

Uniform: Basic operations take unit time regardless of size of operands

Logarithmic: Adding two n digit numbers takes O(n) single digit additions

Multiplying two n digit numbers takes O(n²) single digit multiplications

If the value of a number is N it can be stored in n=log_b N digits in base b.

Recursion, recurrence relations, proofs by induction

Example will be with a Search on a sorted array. Note the handout is a mergesort so in that example, both sides of the array must be called recursively

Algorithm SEARCH (l, u)

//global  A [ : ], x  //
// search for x in A [l:u]

 if l > u then return 0
 mid <--   (l+u) /2  //want floor 
 case
	: x = A (mid):
	     return (mid)

	: x < A (mid):
	     return (SEARCH (l,mid-1))

        : x > A (mid):
	     return (SEARCH (mid+1,u))
// endcase
// end SEARCH

From case statement, divide and conquer,

like a binary search tree

n = u - l + 1

Since we are breaking in two, for ease of calculations, suppose that n is a power of 2.

T (n) < c₂ for n < 1
T(n/2)+c₁ for n > 1

Expand up (without loss of generality, let n = 2^k):

T(1) < c₂
T(2) < T(1) + c₁
T(4) < T(2) + c₁ = T(1) + c₁ + c₁ = T(1) + 2c₁
T(8) < T(4) + c₁ = T(1) + 2c₁ + c₁ = T(1) + 3c₁
T(16) < T(8) + c₁ = T(1) + 3c₁ + c₁ = T(1) + 4c₁

Do we see a pattern? This is important.

T(2^k) < T(1) + kc₁ = c₂ + kc₁

Remember n = 2^k so

log₂ n = log₂ 2^k
Remember what x = log₂y means? Also reminder

log n = k

T(n) < c₂ + c₁log n

Now let's look at it the opposite way (breaking down) (some people see it this way, others see it the other...)

T (n) < c₂ for n < 1
T(n/2)+c₁ for n > 1

This means that

T(n/2) < T(n/4) + c₁

But then
T(n) < T(n/4) + c₁ +c₁

< T (n/8) + c₁ +c₁ +c₁
:
:
< T (n/2^k) + k c₁ Good news, building up or breaking down provide the same pattern

Can we get this k variable out?
If k is large enough such that n/2^k < 1, we can replace T (n/2^k) by c₂ i.e. T (n) < c₂ + k c₁

So, want the smallest k such that : n/2^k < 1

implies 2^k > n

implies k > log₂ n

How did she get that!

logs
If 2^k > n, then log₂ 2^k > log₂ n
but log₂ 2^k is k. Hence k > log₂ n

i.e. k = | log₂n | //should be ceiling log₂n but I cannot make those on browsers (note that I will also not always write log₂ and use log instead)

T(n) < c₂ + c₁log n

= 0 (log n)

Verify using proof by induction

THEOREM:
T(n) < c₂ for n < 1
T(n/2)+c₁ for n > 1 Implies that T(n) = O(log n)

PROOF: By induction ( surprise!)

Base: n = 1
then, T(1) = c₂ = O(1) ; log 1 = 0 also constant O(0)=O(1)

More explicitly, T(n) < c₂ + c₁log n so T(1) < c₂ + 0 < c₂
The recurrance relation states T(n) < c₂ for n < 1; so T(1) < c₂
BASE CASE OK .

Induction hypothesis: Assume THM is true: T(n) = O(log n) for all n < n'.

Induction step:

Suppose n = n' + 1 (how does this differ from us saying n+1 in our earlier induction proofs?)

then, T (n) < T(n/2) + c₁ (by definition of T(n))

since n/2 < n', by induction hypothesis, T (n/2) = 0(log n/2)

which means that T(n/2) < c₃ log n/2 for some constant c₃ and n > some n₀ (by definition of O(g(n)))

Ok, let's look at T(n) again, Remember, T(n) < T (n/2) + c₁

T (n) < c₃ log n/2 + c₁

< c₃ (log n - 1) + c₁

< c₃ log n - c₃ + c₁

= O(log n)

By induction, theorem is true for all n.

DEFN.: f(n) = 0(g(n)) iff there exist two positive constants c and n₀ such that f(n) < c* g(n) for all n > n₀.

OK, OK, I will remind you: c₃log n/2 = c₃(log n - log 2) = c₃(log n - 1)= c₃log n - c₃

Notice that on these recurrances, sometimes it is easier to think in terms of k rather than n. Specifically, we will be using powers of 2 so n=2^k.

Instead of
T(1) = c₂
T(2) = T(1) + c₁
T(4) = T(2) + c₁ = T(1) + c₁ + c₁ = T(1) + 2c₁
T(8) = T(4) + c₁ = T(1) + 2c₁ + c₁ = T(1) + 3c₁
T(16) = T(8) + c₁ = T(1) + 3c₁ + c₁ = T(1) + 4c₁

We think of n = 2^k and (T(n) = T(2^k)) and then the pattern in terms of the number of Recursive steps.
I.E. ,T(1)=T(2⁰)=R(0), T(2)=T(2¹)=R(1)
R(0)= c₂
R(1)= c₂ + c₁
R(2)= c₂ + 2*c₁
R(3)= c₂ + 3*c₁
R(4)= c₂ + 4*c₁
...
R(k)= c₂ + k*c₁
Since n = 2^k, k will be log n and hence it is easy to spot log n recurrances. (sometimes)

See handout. Note a sort is 2T(n/2).

For the example that I show from the exercises, I will make my guess using R(k).
If I haven't already done this, see the handout (a)