CS-4 (LESSON 2) Flashcards
The amount of memory required by an algorithm to run to completion
Space Complexity
The size required to store certain data/variables, that is independent of the size of the problem:
- e.g. name of the data collection
- same size for classifying 2GB or 1MB of texts
Fixed part
Space needed by variables, whose size is dependent on the size of the problem:
- e.g. actual text
- load 2GB of text VS. load 1MB of text
Variable part
Often more important than space complexity
Algorithms running time is an important issue
3-4GHz processors on the market
Time Complexity
varies with the inputs, and typically grows with the size of the inputs.
To evaluate an algorithm or to compare two algorithms, we focus on their relative rates of growth with the increase of the input size.
Running Time
Write a program to implement the algorithm.
Run this program with inputs of varying size and composition.
Get an accurate measure of the actual running time (e.g. system call date).
Experimental Approach
The algorithm has to be implemented, which may take a long time and could be very difficult.
Results may not be indicative for the running time on other inputs that are not included in the experiments.
In order to compare two algorithms, the same hardware and software must be used.
Limitations of Experimental Studies
Based on high-level description of the algorithms, rather than language dependent implementations
Makes possible an evaluation of the algorithms that is independent of the hardware and software environments
Use a Theoretical Approach
High-level description of an algorithm.
More structured than plain English.
Less detailed than a program.
Preferred notation for describing algorithms.
Hides program design issues.
Pseudocode
The basic computations performed by an algorithm
Identifiable in pseudocode
Largely independent from the programming language
Primitive Operations
Based on primitive operations (low-level computations independent from the programming language)
Low Level Algorithm Analysis
By inspecting the code, we can determine the number of primitive operations executed by an algorithm, as a function of the input size.
Counting Primitive Operations
Changing computer hardware / software
The linear growth rate of the running time T(n) is an intrinsic property of algorithm arrayMax
Growth Rate of Running Time
Growth rates of functions:
Linear n
Quadratic n2
Cubic n3
The growth rate is not affected by
___?___ or
lower-order terms
Constant Factors
