Data Structures :: Module 1 Condensed

Module Primer

Given: 2 programs to accomplish a task AND Both are correct
Which do we pick? Two answers-> Smallest, Fastest

Space Complexity
-> Instruction Space
-> Data Space
	- Constants and simple variables
	- Structures, arrays, dynamically allocated memory
-> Environment Stack Space
	- Particularly relevant to recursive programs

Measuring Space Complexity
Two parts
- Fixed portion
- Dynamic portion that depends on input
	- Dynamically allocated space
	- Recursive depth
S (P) = c + SP(instance characteristics)

Time Complexity
Actual time computation is difficult
Estimates are typically good enough
Two major estimates:
	- Operation Counts (Determine one or more operations which we believe are most important (contribute the most) to the time complexity
We then count how many times the operation(s) occur(s).)
	- Step Counts (Determine the number of steps in the program in terms of some input characteristic. Defining a “step” - Any computation unit that is independent of the input characteristics)

Ways to count Steps
Step count table
1. List all statements in program
2. For each statement determine how many steps it is worth and determine its frequency
3. Multiply to produce total steps for the statement
4. Total the steps per statement

Notes about Step Count
- Need to take into account best, worst, average cases
- Take all operations into account, but inexactly.
- Purposes of complexity analysis are
- Compare two programs that compute the same function
- Predict growth in run time as instance characteristics change

Comparing Program Complexities
Suppose one program has a step count of 100n + 10 and one has a step count of 3n + 3.  Which is faster?
Now suppose that one program has a step count of 100n + 10 and one has a step count of 90n + 9.  Which is faster?
What if one is 3n2 + 3 and the other is 
100n + 10?

Comparing Programs
If we have two programs with complexities of c1n2 + c2n and c3n, respectively, we know that:
	c1n2 + c2n > c3n  for all values of n greater than some constant
Breakeven point

Asymptotic Notation
Asymptotic notation gives us a way to talk about the bounds on a program’s complexity, in order to compare that program with others, without requiring that we deal in exact step counts or operation counts

Big Oh Notation
f(n) = O(g(n)) iff positive constants c and n0 exist such that f(n) <= cg(n) for all n, n>=n0.
Provides an upper bound for function f.
Standard functions used for g:

	1		constant

	logn		logarithmic (base irrelevant)

	n		linear

	nlogn		n log n

	n2		quadratic

	n3		cubic

	2n		exponential

	n!		factorial

Omega Notation (Ω)
•	Lower bound analog of big oh notation.
•	Definition:
f(n) = Ω (g(n))  iff positive constants c and n0 exist such that f(n) >= cg(n) for all n, n <= n0.

Theta Notation (Θ)
•	Theta notation can be used when a function can be bounded from above and below by the same function.

Little oh notation
•	Little oh notation (o) applies when an upper bound is not also a lower bound.

Computing Running Times
•	Rule 1: For loops
–	The running time is at most the running time of the statement inside the for loop (including tests) times the number of iterations.
•	Rule 2: Nested loops
–	Analyze inside out.
•	Rule 3: Consecutive statements
–	Add these (meaning the maximum is the one that counts)
•	Rule 4: if/else
–	Running time of an if/else statement is no larger than the time of the test plus the larger of the running times of the bodies of the if and else.
•	In general: work inside out.

Additional Detailed Notes

1. Refer Pages 20 to 60 in Fundamentals of Data Structures in C++ by Ellis Horowitz…
2. Read course material provided.
3. Class notes

Note: Condensed notes for the next module will be put up @ Cyberblitz over the weekend.

Extra Material

In mathematical analysis, and in particular in the analysis of algorithms, to classify the growth of functions one has recourse to asymptotic notations. Knuth advocated the following notations (other notations hold in various contexts, e.g., Landau and Hardy notation):

O-notation (big-oh) 
o-notation (little-oh) 
Ω-notation 
Θ-notation 

The minute details of a function for arbitrary big values of its argument seldom matter. Often it is enough to compare its overall behaviour to standard sets of mathematical function so as qualify the function at hand along a restricted set of significant behaviours, such as bounded, oscillating, divergent, etc..., and to indicate the speed with which it reach this asymptotic behaviour.

For instance if a function tends to zero faster than a square integrable function, it is known that it has a well-defined Fourier transform, no matter what the function actually looks like.
--
The O-notation means that the function is bounded from above (also known as dominated) by a function which varies like f, i.e.,

Thus, f = O(1) means that f is bounded and f = O(x) means that f does not grow faster than linear. It corresponds for functions in asymptotic limit to the relation between numbers.
The o-notation restricts the O-notation to mean that the function is bounded from above but that the bound must not be tight, i.e., the function must grow strictly slower than its o-reference. Formally:

so that for instance 2xn = O(xn) but is not o(xn). (This relation is also pronounced g is negligible w.r.t. f.) Also, xn = o(xm) if n < m while it is O if . It corresponds for functions in asymptotic limit to the relation < between numbers.
The Ω-notation is the counterpart of O-notation for functions bounded from below:

Finally, Θ-notation means there is an asymptotically tight-bound, i.e., that the function really behaves like its reference function:

--
In mathematics and applications, particularly the analysis of algorithms, asymptotic analysis is a method of classifying limiting behaviour, by concentrating on some trend. It is sometimes expressed in the language of equivalence relations. For example, given complex-valued functions f and g of a natural number variable n, one can write

to express the concept that
.
This defines an equivalence relation; and the equivalence class of f consists of all functions g with similar behaviour to f, in the limit.

Asymptotic notation has been developed to provide a convenient language for the handling of statements about order of growth. It is also called Landau notation, since it became popular first in research in analytic number theory, from about 1900 onwards, introduced by Edmund Landau (originated though by Paul Bachmann). See also Big O notation, for a treatment more from the point of view of analysis of algorithms. The asymptotic point of view is basic in computer science, where the question is typically how to describe the resource implication of scaling-up the size of a computational problem, beyond the 'toy' level.

An asymptotic expansion of a function f(x) is in practice an expression of that function in terms of an infinite series, the partial sums of which do not (necessarily have to) converge; but such that taking any initial partial sum provides an asymptotic formula for f. The idea is that successive terms provide a more and more accurate description of the order of growth of f.

--
Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. More precisely, it is used to describe an asymptotic upper bound for the magnitude of a function in terms of another, usually simpler, function. It has two main areas of application: in mathematics, it is usually used to characterize the residual term of a truncated infinite series, especially an asymptotic series, and in computer science, it is useful in the analysis of the complexity of algorithms.

It was first introduced by German number theorist Paul Bachmann in 1894, in the second volume of his book Analytische Zahlentheorie (the first volume of which came out in 1892, and did not contain big O notation). The notation was popularized in the work of another German number theorist Edmund Landau, hence it is sometimes called a Landau symbol.

--