CC4 first quiz

Space Complexity

The space needed by a program is seen to be the sum of two components

ALGORITHMS

a finite sequence of instructions, each of which has a clear meaning and can be performed with a finite amount of effort in a finite length of time

Specification, Verification, Performance analysis

The technical terms normally used for these three aspects are:

Time Complexity

Try to guess the time complexity experimentally

RUNNING TIME ANALYSIS

It is the process of determining how processing time increases as the size of the problem (input size) increases.

RATE OF GROWTH

rate at which the running time increases as a function of input

Worst case Running Time

an upper bound on the running time for any input. Knowing it gives us a guarantee that the item does not occur in data.

Average case Running Time

entails "knowing all possible input sequences, the probability distribution of occurrence of these sequences, and the running times for the individual sequences”.

Best case Running time

if elements are already sorted for a specific algorithm

Time-Space Tradeoff

is a way of solving a problem or calculation in less time by using more storage space (or memory), or by solving a problem in very little space by spending a longtime.

Design patterns

describe the design of algorithms, rather the design of data structures

List

ordered sequence of data items known as elements

Homogenous

implies all elements must be of the same type and have the same structure

Finite

means that each array contains a fixed number of element

Ordered

means that elements are organized in sequence.