Compare

• Ease of programming
• Time efficiency
• Space efficiency

Express complexity as a function of the "size" of a problem

Space Complexity: amount of memory a program needs to run to completion
(in book see page 15; I will focus on time but sometimes bring in space issues)

Time Complexity: amount of computer time a program needs to run to completion

When we measure time and space complexity of a program, we need to consider what happens as the number or size of data (for input or output) increases...i.e., what are the characteristics of the data for this instance which will affect the values for time and space?

Time analysis is based on the size of the data set.

One Example: the length of a string affects the time it takes to search for a character in a string

Basically, the measure of the size of a problem depends on the number of data items.

T (n) = n reads + n additions

anything else?

To do time complexity, we do not want to simply measure the run of a program, but to determine mathematically how changes in data (for the given procedure) will change the time.

What happens as the size increases ?

• Worst case analysis
• Statistically average case analysis

Asymptotic (worst case) complexity:

Algorithm ADDPOS
	/* add positive data items */
        ACCUM = 0
	while (more data items) do
		read data_item
		if data_item > 0
			then ACCUM = ACCUM + data_item

Program Step - a meaningful segment of a program that has an execution time that is independent of the instance characteristics

step counts are useful since they tell us how the run time changes with instance characteristics (e.g., for i = 1 to n ... if n doubles, time doubles)

Note: Step counts do not necessarily reflect the complexity of the statement. For example some books count a function call as one step count

Steps/execution (s/e) is the amount of which the count changes as a result of execution (see page 19-24 and Sum(a,n))

The time complexity of a program is given by the number of steps taken by the program to compute the function it is written for. (i.e., s/e)

[Do some T(n) ]

a = b; x = y; for (i= 1; i <= n, i++) { temp = a[i]; a[i] = a[i + 1]; a[i +1] = temp; }

Once an expression is obtained based on the data set, the order of the algorithm is given by the dominating term.

For example:

If T(n) = 2 + 3n, we say the algorithm is O(n) or of Order n
If T(n) = 0.5 * 2ⁿ + nlog₂ n + 600,040 then the algorithm is O(2ⁿ )

Thus, it is easy to see that the coefficients or constants are insignificant.

Asymptotic Notation

Def. f(n) = O(g(n)) iff there exists positive constants c and n_o such that f(n) < cg(n) for all n , n > n_o (g is upper bound)

look at Example 1.11 on page 29

Verify:

let n_o = 1 and c = 4
for n > 1,        (n +1)² < 4n²

T(n) is O(n² ) for some program means there are positive constants c and n_o such that for n > n_o we have T(n) < cn²

verify T(n) = 3n³ + 2n² is O(n³) (what does that mean?)

T(n) = 3n³ + 2n² < cn³ let c= 5, n_o = 1, then for all n > 1
3n³ + 2n² < 5n³
2n²<2n³
n²< n³
1 < n

is T(n) also O(n⁴) ?

So, f(n) = O(n^m) (assuming that m is fixed)

DONE

WHY?
Remember:
f(n) = O(g(n)) iff there exists positive constants c and n_o such that f(n) < cg(n) for all n , n > n_o
Our g(n) is n^m, let be   c

One can always "play" for a proper n_o and c. You only need one to work to show the definition holds, so pick one that is easy to allow you to verify.

f(n) = O(g(n)) says g(n) is an upper bound ... does not say how good. To be informative, want smallest (least upper bound)

another example:

What about

f(n) = 6 * 2ⁿ + n
f(n) = 6 * 2ⁿ + n is O(2ⁿ) since
f(n) = 6 * 2ⁿ + n < 7 * 2ⁿ for n > 4 (what is c, n_o?)

Now get O(n) and verify