ACE Take-Away: Lect No.2 Efficiency
Ch'i YU Lv3
  2022-09-28 18:26:44 2022-09-28 18:26      4 Mins  

Take-Away Notes for Module COMP2048.

Pseudocode, Running Time Analysis and Big-Oh() Series

  • Proofread
  • Reviewed
  • Add Figures
  • Complete Sample Proofs

Pseudocode

Method Declaration

1
2
3
Algorithm method(arg [, arg ...] )
    Input ...
    Output ...

Control Flow

1
2
3
4
if ... then ... [else ...]
while ... do ...
repeat ... until ...
for ... do...

note: Use Indentation to replace Braces

Method Call

1
method(arg [, arg ...])

Return Value

1
return expression

Expression Notation

Assignment:

Equality Testing:

note: Superscriptions and other mathematical formatting allowed

Running Time Analysis

  • Focus on the relationship between running time of algorithm & size of its input
  • Characterized as a function of the input size for an algorithm

Running Time

Affected by:

  • Input Size
  • Hardware Environment (e.g. Processor / Clock Rate / Memory / Disk)
  • Software Environment (e.g. Operating System / Programming Language)

Experimental Analysis

  1. Write a program to implement the algorithm
  2. Run the program to perform independent experiments with inputs of varying size
  3. Plot the results of input size & running time
  4. (Extra) Apply statistical analysis that seeks to fit the best function of input size to the experimental data

Limitations:

  • Same hardware & software must be applied to compare algorithms;
  • Results may not be indicative of the running time on other inputs not included in the experiment;
  • Implementation of algorithm is compulsory;

Theoretical Analysis

Advantages

  • High Level Description
  • Characterize Running Time as a function of the input size n
  • Takes all possible(legal) inputs into account
  • Evaluation independent of hardware / software environment

Primitive Operations

Definition:

  • Basic computations performed by an algorithm
  • Independent from programming languages
  • Exact definition is unnecessary
  • Assumed to take a constant amount of time in RAM(Random Access Machine) Model

Components & Examples:

  • Assign a value to a variable
  • Following an object reference
  • Performing an arithmetic operation
  • Comparing two numbers
  • [!] Accessing a single element of an array by index
  • [!] Calling a method
  • [!] Return from a method

RAM(Random Access Machine)

Components:

  • CPU
  • (Potentially) unbounded & numbered memory cells

Estimating Theoretical Running Time

TBC. See also in the slides (Page 17-18) for more details.

Just take care: Treat loops / method calling / method returning CAUTIOUSLY!

Big-Oh Series

Concerns: Worst Case

Samples: , , , , , , ,

Usage:

  • Rank functions / algorithms according to the growth rates of input size & running time;
  • Gives an upper bound on the growth rate of a function;

Note: means that the growth rate of is no more than the growth rate of .

Example Process:

e.g. For Algorithm arrayMax(mentioned in slides (Page 17-18)) with primitive operations to execute in the worst case:

Primitive operations are assumed to take a constant amount time in the RAM model as mentioned before, which is denoted as ;

Let denotes the worst case time of arrayMax:

Thus ;

Thus is a linear function, arrayMax runs in linear time;

Note: is affected by constant factors,

e.g. hardware / software environment, lower-ordered terms of

but the growth rate of which is independent(an intrinsic property of the corresponding algorithm)

Big-Oh: General Proofs

Let and be functions mapping positive integers to positive real numbers.

Thus we say is if there is a real constant and an integer constant such that for every , .

aka. the growth of the real running time is never under estimated.

f(n) is O(g(n)) g(n) is O(f(n))
g(n) grows more Yes No
f(n) grows more No Yes
Same Growth Yes Yes

Note: Big-Oh Series are NOT related to derivative & differentiate! [!]Note: Proofs are ommited until later. -- 2022/09/28

Big-Oh Rules:

  1. Drop lower-order terms of ;
  2. Drop constant factors of ;

e.g. ""; "";

Asymptotic Algorithm Analysis

Purpose: determines the running time in Big-Oh Notation();

Perform / Deliver 1. Find the worst-case number of primitive operations executed as a function of the input size; 2. Express this function with Big-Oh notation; e.g. arrayMax runs in time;

Big-Oh Series in A Nutshell

Prerequisites: Let and be functions mapping positive integers to positive real numbers.

Big-Oh

is if is asymptotically less than or equal to g(n).

i.e. We say that is ,

if there is a real constant and an integer constant

such that for every :

i.e.

Big-Omega

is if is asymptotically greater than or equal to g(n).

i.e. We say that is ,

if there is a real constant and an integer constant

such that for every :

i.e.

Big-Theta

is if is asymptotically equal to g(n).

i.e. We say that is ,

if there are real constants , and an integer constant

such that for every :

i.e.

Little-Oh

is if is asymptotically, strictly less than g(n).

i.e. We say that is ,

if for all positive real constant , there exists an integer constant

such that for every :

i.e.