You want to determine if a string is a palindrome (read the same backward and forward).

You will compare characters from the opposite ends.

The basic operation is a character-character comparison.

1) B(n) = ? comparisons When does it happen? Give an example string.

2) W(n) =? comparisons (for odd and even lengths) When does it happen? Give example strings.

1. What do you think is F(n) of the problem of is this a palimdrome? = ? comparisons

Explain why.

Now, think about reversing a string in place.

4) For this problem, what do you count as operations?

5) What is its W(n) =? Explain why.

-------------------------------------------------------------------------------

examples

Amount of Work/Time Complexity Example: Sequential Search

Sequentially search through a list of n elements looking for x.

The basic operation is the comparison of x against a list element.

W(n) = n comparisons Why? We have to compare x with every list entry

i.e. when x is the last element or not in the list

B(n) = 1 comparison Why? We find x right away.

i.e. when x is the first element.

Lets see how A(n) is computed using probabilities. We will divide it into 2 cases:

A(n) when x is in the list

= (n + 1) / 2 if all elements are distinct and any order is equally likely

WHY? If x is in location i, it takes i comparisons.

• Probability that x is in location i is 1/n.
• Sum-of 1/n *i for i = 1 to n

Since Sum-of i for i = 1 to n is n(n+1)/2, the answer is (n+1)/2.

[Warning: If there are many duplicates, it is difficult to determine the probability of x being in location i]

A(n) when x is not in the list

= n comparisons

Now we combine the two average cases:

A(n) when x may or may not be in the list

= Prob(success)*time(success) + Prob(fail)*time(fail)

= q*(n + 1)/2 + (1-q)*n comparisons

where q is the probability that x is in the list

1-q is the probability that x is not in the list

e.g.

If q = 1/2 (i.e. 50-50 chance that x is in the list)

then A(n) = (n+1)/4 + n/2 comparisons (about 3/4 of the entries)