Algorithmic complexity
How required time changes as the problem size increases
Time cost equation
t = Cg(n) –> O(g(n))
n- size of problem
C - constant
g - function
O(1)
Algorithm constant in time
t = O(1)
time required for the algorithm is independent of the problem size n
O(n^k)
Polynomial in time
O(log n)
Logarithmic in time
O(n log n)
Log - linear in time
Examples: Quick sort and fast Fourier Transform
O(c^n)
Exponential in time
Algorithm becomes expensive (time cost) for large n, generally little to no practical use
Complexity in terms of space
How the computer memory required by an algorithm will change with problem size
How do you determine the complexity of an algorithm
Count the number of operations
What is the complexity of multiplying an array by a scalar
cost for x[i] = a*x[i] is O(1) for each i, so overall cost O(n)
What is the complexity of multiplying a nxm matrix by scalar a
total cost O(n) for each i, and loop i m times, so total cost is O(mn) and if m=n then O(n^2)
What do we need to consider when assessing an algorithm?
Best case complexity
Worst case complexity
Average case complexity
What is the cost of operations (+,-,*,/)
O(1)
Linear search
Search algorithm that iterates over an array one element at a time looking for a target value
What is the best-case time complexity of linear search?
Value found in the first position - O(1)
What is the worst case time complexity of linear search?
Value is not in array, so every element must be checked - O(n)
What is the average-case time complexity of linear search?
On average, value found halfway through the array - O(n)
Why is the average case of linear search O(n) and not O(n/2)
Constant factors are ignored in ‘Big-O’ notation
What is binary search?
Search algorithm that repeatedly divides a sorted array in half to find a target value
What is the best-case time complexity of binary search?
O(1) - the value is found at the middle of the first check
What is the worst-case time complexity of binary search?
O(log n) - the array is repeatedly halved until the value is found or ruled out
What is the average-case time complexity of binary search?
O(log n)
Is linear or binary search faster for large arrays?
Binary, as O(log n) grows slower than O(n)
Why can linear search be faster than binary search for small arrays?
Linear search has a smaller constant factor and benefits from CPU cache optimisation
-
02 Control Statements11
-
03 Types, type conversions and floating point arithmetic35
-
04 Functions9
-
05 Library functions8
-
06 Data structures23
-
07 Numerical Computation19
-
08 Plotting4
-
09 Error handling and testing9
-
10 Algorithms11
-
11 Complexity34
-
12 Object-oriented Design28
-
13 Compiled and Interpreted Languages26
