CITS2200 - Lecture 6

← Back to Home

CITS2200 - Lecture 5
Complexity Analysis of Algorithms - Slides

Running Time

• Algorithms transform input objects to output objects
• Running time increases as input grows
  • Average case time is difficult to determine
  • Thus, we focus on worst case running time

It is impossible to represent exact run time because it depends on so many factors (e.g. your computer, the programming language, etc.) thus in complexity analysis, we need to ignore all these factors to give a mathematical representation of run time to allow us to evaluate speed of an algorithm independent of the hardware/software environment

---

Complexity Analysis of Algorithms - Slides cont.

Graphing Complexity

• Most complexity graphs use a logarithmic scale

  

  • Slope corresponds to growth rate
  • We do not draw left side of the graph because our values can never be negative

• There are 7 functions that often appear in algorithm analysis:

  • Constant $\approx 1$
  • Logarithmic $\approx \log n$
  • Linear $\approx n$
  • N-Log-N $\approx n\log n$
  • Quadratic $\approx n^2$
  • Cubic $\approx n^3$
  • Exponential $\approx 2^n$

Estimating Running Time

• Primitive operations are basic computations performed by an algorithm
  e.g. evaluating an expression, assigning a value to a variable, etc.

We could count primitive operations in pseudocode to estimate run time, but this is flawed method as every operation has a wildly variable run time

• But for the sake of simplicity, we assume that any primitive operation only counts as one operation step
• Thus, even though calling a function is much more complex than just initialising a variable, we still only count 1 operation for each

Maximum number of primitive operations executed by an algorithm is usually a function of the input size:

• e.g. if in a section of pseudocode you have a loop such as ‘for val in data:’, this would take $2n$ operations where $n$ represents the number of values in data
  • $2$ is because there are two operations inside the loop

Overall, this way of estimating is not very useful as it becomes tedious if your algorithm has many line and is also very inaccurate

Counting operations to estimate complexity is meaningless, as complexity is always dictated by the highest order polynomial in your function:

• If you identify in a 1000 line algorithm two nested for loops that both run from 1 to n, these loops combined have a complexity of $n^2$
• No matter how many other lines are in the algorithm, they will have complexity of $c\times n$ where $c$ is some constant
• $cn$ is insignificant compared to $n^2$, so we just say the algorithm has complexity of $n^2$

Comparison of Insertion and Merge-Sort

• Insertion sort complexity → $O(n^2)$
• Merge-sort complexity → $O(n\log n)$

• We can see that merge-sort is much better than insertion sort as its growth rate is far lower
  e.g. to sort a million items, insertion sort might take 70 hours while merge-sort only takes 40 seconds
• However, in practice, we would probably use merge-sort to sort through a large array until it becomes small enough for use to use insertion sort which is more efficient at small values of $n$

Big Oh Notation and Tighter Bounds

• Given functions $f(n)$ and $g(n)$, if $f(n)$ is bounded from above by $g(n)$:
  $f(n)=O(g(n))$
• Mathematically it looks like this:
  $f(n)\le cg(n)\text{for}n\ge n_0$
  $c$ and $n_0$ are positive constants

You can describe the complexity of an algorithm using a function it is bounded from above by:

• e.g. insertion sort normally has complexity $O(n^2)$, but it also has complexity $O(n^4)$
• This statement is not incorrect, only imprecise
  • A more precise function is known as a tighter bound

Big O notation tells you an upper bound that is bounding a function of an algorithms run time

See: Math to Review

---

CITS2200 - Lecture 7