You've probably heard people talk about a fast or efficient algorithm
for executing your particular task,
but what exactly does it mean for an algorithm to be fast or efficient?
Well, it's not talking about a measurement in real time,
like seconds or minutes.
This is because computer hardware
and software vary drastically.
My program might run slower than yours,
because I'm running it on an older computer,
or because I happen to be playing an online video game
at the same time, which is hogging all my memory,
or I might be running my program through different software
which communicates with the machine differently at a low level.
It's like comparing apples and oranges.
Just because my slower computer takes longer
than yours to give back an answer
doesn't mean you have the more efficient algorithm.
>> So, since we can't directly compare the runtimes of programs
in seconds or minutes,
how do we compare 2 different algorithms
regardless of their hardware or software environment?
To create a more uniform way of measuring algorithmic efficiency,
computer scientists and mathematicians have devised
concepts for measuring the asymptotic complexity of a program
and a notation called 'Big Ohnotation'
for describing this.
The formal definition is that a function f(x)
runs on the order of g(x)
if there exists some (x) value, x₀ and
some constant, C, for which
f(x) is less than or equal to
that constant times g(x)
for all x greater than x₀.
>> But don't be scared away by the formal definition.
What does this actually mean in less theoretical terms?
Well, it's basically a way of analyzing
how fast a program's runtime grows asymptotically.
That is, as the size of your inputs increases towards infinity,
say, you're sorting an array of size 1000 compared to an array of size 10.
How does the runtime of your program grow?
For example, imagine counting the number of characters
in a string the simplest way
by walking through the whole string
letter-by-letter and adding 1 to a counter for each character.
This algorithm is said to run in linear time
with respect to the number of characters,
'n' in the string.
In short, it runs in O(n).
Why is this?
Well, using this approach, the time required
to traverse the entire string
is proportional to the number of characters.
Counting the number of characters in a 20-character string
is going to take twice as long as it takes
to count the characters in a 10-character string,
because you have to look at all the characters
and each character takes the same amount of time to look at.
As you increase the number of characters,
the runtime will increase linearly with the input length.
>> Now, imagine if you decide that linear time,
O(n), just wasn't fast enough for you?
Maybe you're storing huge strings,
and you can't afford the extra time it would take
to traverse all of their characters counting one-by-one.
So, you decide to try something different.
What if you would happen to already store the number of characters
in the string, say, in a variable called 'len,'
early on in the program,
before you even stored the very first character in your string?
Then, all you'd have to do now to find out the string length,
is check what the value of the variable is.
You wouldn't have to look at the string itself at all,
and accessing the value of a variable like len is considered
an asymptotically constant time operation,
or O(1).
Why is this? Well, remember what asymptotic complexity means.
How does the runtime change as the size
of your inputs grows?
>> Say you were trying to get the number of characters in a bigger string.
Well, it wouldn't matter how big you make the string,
even a million characters long,
all you'd have to do to find the string's length with this approach,
is to read out the value of the variable len,
which you already made.
The input length, that is, the length of the string you're trying to find,
doesn't affect at all how fast your program runs.
This part of your program would run equally fast on a one-character string
and a thousand-character string,
and that's why this program would be referred to as running in constant time
with respect to the input size.
>> Of course, there's a drawback.
You spend extra memory space on your computer
storing the variable
and the extra time it takes you
to do the actual storage of the variable,
but the point still stands,
finding out how long your string was
doesn't depend on the length of the string at all.
So, it runs in O(1) or constant time.
This certainly doesn't have to mean
that your code runs in 1 step,
but no matter how many steps it is,
if it doesn't change with the size of the inputs,
it's still asymptotically constant which we represent as O(1).
>> As you can probably guess,
there are many different big O runtimes to measure algorithms with.
O(n)² algorithms are asymptotically slower than O(n) algorithms.
That is, as the number of elements (n) grows,
eventually O(n)² algorithms will take more time
than O(n) algorithms to run.
This doesn't mean O(n) algorithms always run faster
than O(n)² algorithms, even in the same environment,
on the same hardware.
Maybe for small input sizes,
the O(n)² algorithm might actually work faster,
but, eventually, as the input size increases
towards infinity, the O(n)² algorithm's runtime
will eventually eclipse the runtime of the O(n) algorithm.
Just like any quadratic mathematical function
will eventually overtake any linear function,
no matter how much of a head start the linear function starts off with.
If you're working with large amounts of data,
algorithms that run in O(n)² time can really end up slowing down your program,
but for small input sizes,
you probably won't even notice.
>> Another asymptotic complexity is,
logarithmic time, O(log n).
An example of an algorithm that runs this quickly
is the classic binary search algorithm,
for finding an element in an already-sorted list of elements.
>> If you don't know what binary search does,
I'll explain it for you really quickly.
Let's say you're looking for the number 3
in this array of integers.
It looks at the middle element of the array
and asks, "Is the element I want greater than, equal to, or less than this?"
If it's equal, then great. You found the element, and you're done.
If it's greater, then you know the element
has to be in the right side of the array,
and you can only look at that in the future,
and if it's smaller, then you know it has to be in the left side.
This process is then repeated with the smaller-size array
until the correct element is found.
>> This powerful algorithm cuts the array size in half with each operation.
So, to find an element in a sorted array of size 8,
at most (log₂8),
or 3 of these operations,
checking the middle element, then cutting the array in half will be required,
whereas an array of size 16 takes (log₂16),
or 4 operations.
That's only 1 more operation for a doubled-size array.
Doubling the size of the array
increases the runtime by only 1 chunk of this code.
Again, checking the middle element of the list, then splitting.
So, it's said to operate in logarithmic time,
O(log n).
But wait, you say,
doesn't this depend on where in the list the element you're looking for is?
What if the first element you look at happens to be the right one?
Then, it only takes 1 operation,
no matter how big the list is.
>> Well, that's why computer scientists have more terms
for asymptotic complexity which reflect the best-case
and worst-case performances of an algorithm.
More properly, the upper and lower bounds
on the runtime.
In the best case for binary search, our element is
right there in the middle,
and you get it in constant time,
no matter how big the rest of the array is.
The symbol used for this is Ω.
So, this algorithm is said to run in Ω(1).
In the best case, it finds the element quickly,
no matter how big the array is,
but in the worst case,
it has to perform (log n) split checks
of the array to find the right element.
Worst-case upper bounds are referred to with the big "O" that you already know.
So, it's O(log n), but Ω(1).
>> A linear search, by contrast,
in which you walk through every element of the array
to find the one you want,
is at best Ω(1).
Again, the first element you want.
So, it doesn't matter how big the array is.
In the worst case, it's the last element in the array.
So, you have to walk through all n elements in the array to find it,
like if you were looking for a 3.
So, it runs in O(n) time
because it's proportional to the number of elements in the array.
>> One more symbol used is Θ.
This can be used to describe algorithms where the best and worst cases
are the same.
This is the case in the string-length algorithms we talked about earlier.
That is, if we store it in a variable before
we store the string and access it later in constant time.
No matter what number
we're storing in that variable, we'll have to look at it.
The best case is, we look at it
and find the length of the string.
So Ω(1) or best-case constant time.
The worst case is,
we look at it and find the length of the string.
So, O(1) or constant time in worst case.
So, since the best case and worst cases are the same,
this can be said to run in Θ(1) time.
>> In summary, we have good ways to reason about codes efficiency
without knowing anything about the real-world time they take to run,
which is affected by lots of outside factors,
including differing hardware, software,
or the specifics of your code.
Also, it allows us to reason well about what will happen
when the size of the inputs increases.
>> If you're running in O(n)² algorithm,
or worse, a O(2ⁿ) algorithm,
one of the fastest growing types,
you'll really start to notice the slowdown
when you start working with larger amounts of data.
>> That's asymptotic complexity. Thanks.