Algorithms: Running Time and Input Size

• An algorithm is a step-by-step procedure for solving a problem in a finite amount of time.

Running Time and Input Size

• Running time describes how well an algorithm performs as the input size grows.
• Algorithm running time typically increases with input size.
• Algorithms can perform differently with the same input size but different contents or order

Best, Worst, and Average Cases

• With the same input size of n elements, "best case" occurs with minimum steps, "worst case" with maximum steps, and "average case" with an average number of steps.
• Average case time can be difficult to determine.
• Best case occurs when item "e" is the first element in array A, so the 'if' runs once.
• Worst case occurs when item "e" does not exist in A, so the 'if' runs n times.
• Average case occurs when e exists in the middle of array A, so the 'if' runs about n/2 times.
• Generally focusing on the "worst-case" running time is easier to analyze.
• It is possible to estimate the maximum time for the algorithm to finish, which is crucial to applications such as games, finance and robotics

Running Time Analysis

• There are 2 techniques: experimental studies and theoretical analysis.

Experimental Studies

• Process: write a program implementing the algorithm, run the program with inputs of varying size and composition, use programming's language time method to get an accurate measurement of the actual running time and plot the results.
• Limitations: no hardware to process huge amounts of inputs and difficult to find complete or sufficient inputs to produce indicative results.
• It is also difficult to find the same hardware and software to compare algorithms in a fair manner.

Theoretical Analysis

• It uses pseudocode; characterizes running time as a function of the input size, n.
• Advantages: it takes into account all possible inputs.
• It allows evaluation the speed of an algorithm independent of the hardware/software.

Pseudocode

• High-level description of an algorithm.
• Less detailed than a programming language.
• There is more than one way to write a pseudocode.
• Example: find max element of an array.

Primitive Operations

• Basic computations performed by an algorithm.
• Identifiable in pseudocode.
• They are largely independent from the programming language.
• The exact definition is not important; it is assumed to take a constant amount of time.
• Examples: performing an arithmetic operation, assigning a value to a variable, indexing into an array, calling a method, returning from a method and comparing 2 variables.

Counting Primitive Operations

• Determine the maximum number of primitive operations executed by an algorithm (worst case) as a function of the input size.
• Counting primitive operations in detail is for illustration only.
• In the worst case, arrayMax executes 7n - 2 primitive operations whereby the 'if' loop is always true.
• In the best case, arrayMax executes 5n primitive operations whereby the ‘if’ loop is always false.
• T(n) represents the worst-case time of arrayMax.
• T(n)=7n-2

Growth Rate of Running Time

• Changing the hardware/software environment affects T(n) by a constant factor, but does not alter the growth rate of T(n).
• n, 10n and 100n grow at the same rate.

Growth Rates of Functions

• From lowest to highest: constant 1, logarithmic log n, linear n, N-Log-N n log n, quadratic n², cubic n³ and exponential 2"

Big-Oh Notation

• Given functions f(n) and g(n), f(n) is O(g(n)) if there are positive constants c and n₀ such that f(n) ≤ cg(n) for n ≥ n₀.
• Example: 2n + 10 is O(n)

Big-Oh Example

• Example: n² is not O(n)

Big-Oh and Growth Rate

• The big-Oh notation gives an upper bound on the growth rate of a function.
• "f(n) is O(g(n))" means that f(n)'s growth rate is no more than g(n)'s growth rate.
  • If g(n) grows more, then f(n) is O(g(n)) is "yes", g(n) is O(f(n)) is "no".
  • If f(n) grows more, then f(n) is O(g(n)) is "no", g(n) is O(f(n)) is "yes".
  • If growth is the same, then f(n) is O(g(n)) is "yes", g(n) is O(f(n)) is "yes".

Big-Oh Rules

• If f(n) is a polynomial of degree d, then f(n) is O(n^d); drop lower-order terms and constant factors.
• Use the smallest possible class of functions.
  • e.g. "2n is O(n)" instead of "2n is O(n²)"
• Use the simplest expression of the class.
  • e.g. "3n + 5 is O(n)" instead of "3n + 5 is O(3n)"

Asymptotic Algorithm Analysis

• Determines running time in big-Oh notation.
• It is performed by finding the worst-case number of primitive operations executed as a function of the input size and expressing this function with big-Oh notation.
• Example: algorithm arrayMax executes at most 7n - 2 primitive operations.
• To simplify, constant factors and lower-order terms are eventually dropped.

The Importance of Asymptotics

• An algorithm with an asymptotically fast running time (low growth rate) can process more inputs than an algorithm with an asymptotically slow running time (high growth rate).
• For example, the maximum problem size (n) given 1 second running time:
  • O(n) can process 2,500
  • O(n log n) can process 4,096
  • O(n^2) can process 707
  • O(n^4) can process 31
  • O(2^n) can process 19

Computing Prefix Sums

• Another example: prefix sums.
• The i-th prefix sum of an array X is sum of the first (i + 1) elements of X: - A[i] = (X[0] + X[1] + ... + X[i])
• Two algorithms with different running time can be used for computing prefix sums.
  • PrefixSum1 runs in O(n²) time.
  • PrefixSum2 runs in O(n) time.

PrefixSums1 (Quadratic)

• This algorithm computes prefix averages in quadratic time n².

Arithmetic Progression

• The sum of the first n integers
  • (1 + 2 + ...+ n) is n(n + 1) / 2.
• The algorithm prefixSum1 runs in O(n²) time.

PrefixSum2 (Linear)

• This algorithm computes prefix sums in linear time n with previous sum.

Intuition for Asymptotic Notation

• Big-Oh: f(n) is O(g(n)) if f(n) is asymptotically less than or equal to g(n).
• big-Omega: f(n) is Ω(g(n)) if f(n) is asymptotically greater than or equal to g(n).
• big-Theta: f(n) is Θ(g(n)) if f(n) is asymptotically equal to g(n).
• little-oh: f(n) is o(g(n)) if f(n) is asymptotically strictly less than g(n)
• little-omega: f(n) is ω(g(n)) if is asymptotically strictly greater than g(n)

Time Complexity

• Time complexity, T(n), refers to the use of asymptotic notation (O,Θ,Ω, o,ω) in denoting running time.
• If 2 algorithms accomplish the same task with different time complexities:
  • One is faster than another.
  • As input n increases further, the performance difference becomes more obvious.
• Faster algorithm is generally preferred.

Time Complexity Comparison

• A fast algorithm has a low time complexity, while a slow algorithm has a high time complexity.
• Ranking of selected time complexities from fastest to slowest:
  • Constant 1 (lowest T(n), fastest speed), Logarithmic log n, Linear n, N-Log-N n log n, Quadratic n², Cubic n³, Exponential 2" (highest T(n), slowest speed).