Usually there is more than one way to solve a problem.

This means there is more than one solution... How do we decide which is better?

Compare

• Ease of programming
• Time efficiency
• Space efficiency

Space Complexity: amount of memory a program needs to run to completion (in book see pages 68-75; I will focus on time - in fact, skip to Section 2.3.4)

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

instance characteristics:
A given program can be run on many different input sets.
A given run on a given program with a given set of data is an instance.

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?

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

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

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

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 (in this book a function call is only one step). Steps/execution (s/e) is the amount count changes as a result of execution (see page 94 and sum(a,m))

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)

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

HELP with summation and induction review

[Do some T(n) ]

Use "Big O" to describe time (or space) complexity. "O" for order of the algorithm.

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.

for (int i=1; i <= n; i++) for (int j=1; j <= i; j++) for (int k=1; k <= j; k++) x = x + 1;

(Later we will also get O(n) and verify.)

calculation of the above summations: (go backwards)

O(n³)

Try another

for (int i=1; i <= n; i++) x = x + 1; for (int j=1; j <= n; j++) { x = x + 1; for (int k=1; k <= j; k++) x = x + 1; }

Proof for the above.

Sometimes you don't know what a summation equals:
Use proof by induction to show:

Proof by induction

Show base case
Assume true for n
Prove true for n+1