Comprehensive Overview of Algorithms and Data Structures Course

this is a full-length course from treehouse we at free code camp are longtime fans of their learning platform

they were kind enough to let our non-profit make this course freely available on our youtube channel if you

like this course treehouse has a lot more courses like this one the link is in the description

along with time codes to the different sections in this course [Music]

hi my name is passan i'm an instructor here at treehouse and welcome to introduction to algorithms

whether you are a high school or college student a developer in the industry or someone who is learning to code you have

undoubtedly run into the term algorithm for many people this word is kind of scary it represents this body of

knowledge that seems just out of reach only people with computer science degrees know about algorithms now to

others this brings up feelings of imposter syndrome you might already know how to code but

you're not a real developer because you don't know anything about algorithms personally it made me frame certain jobs

as above my skill level because the interview contained algorithm questions well whatever your reasons are in this

course our goal is to dispel all those feelings and get you comfortable with the basics of algorithms

like any other subject i like to start my courses with what the course is and is not

in this course we're going to cover the very basic set of knowledge that you need as a foundation for learning about

algorithms this course is less about specific algorithms and more about the tools you

will need to evaluate algorithms understand how they perform compare them to each other and make a

statement about the utility of an algorithm in a given context now don't worry none of this will be

theoretical and we will learn these concepts by using well-known algorithms in this course we will also be writing

code so i do expect you to have some programming experience if you intend to continue with this topic

you can definitely stick around even if you don't know how to code but you might want to learn the basics of programming

in the meantime in this course we will be using the python programming language python reads

a lot like regular english and is the language you will most likely encounter when learning about algorithms these

days if you don't know how to code or if you know how to code in a different language

check out the notes section of this video for links to other content that might be useful to you

as long as you understand the fundamentals of programming you should be able to follow along pretty well

if you're a javascript developer or a student who's learning javascript for example chances are good that you'll

still be able to understand the code we write later i'll be sure to provide links along the way if you need anything

to follow up on let's start with something simple what is an algorithm

an algorithm is a set of steps or instructions for completing a task this might sound like an over

simplification but really that's precisely what an algorithm is a recipe is an algorithm your morning

routine when you wake up is an algorithm and the driving directions you follow to get to a destination is also an

algorithm in computer science the term algorithm more specifically means the set of steps

a program takes to finish a task if you've written code before any code really generally speaking you have

written an algorithm given that much of the code we write can be considered an algorithm what do

people mean when they say you should know about algorithms now consider this

let's say i'm a teacher in a classroom and i tell everyone i have an assignment for them on their desks they have a

picture of a maze and their task is to come up with a way to find the quickest way out of the maze

everyone does their thing and comes up with a solution every single one of these solutions is a

viable solution and is a valid example of an algorithm the steps one needs to take to get out of the maze but from

being in classrooms or any group of any sort you know that some people will have better ideas than others we all have a

diverse array of skill sets over time our class picks the best of these solutions and any time we want to

solve a maze we go with one of these solutions this is what the field of algorithms is about

there are many problems in computer science but some of them are pretty common regardless of what project you're

working on different people have come up with different solutions to these common

problems and over time the field of computer science has identified several that do the job well for a given task

when we talk of algorithms we're referring to two points we're primarily saying there's an

established body of knowledge on how to solve particular problems well and it's important to know what the solutions are

now why is it important if you're unaware that a solution exists you might try to come up with one

yourself and there's a likelihood that your solution won't be as good or efficient whatever that means compared

to those that have been thoroughly reviewed but there's a second component to it as

well part of understanding algorithms is not just knowing that an algorithm exists

but understanding when to apply it understanding when to apply an algorithm requires properly understanding the

problem at hand and this arguably is the most important part of learning about algorithms and data structures

as you progress through this content you should be able to look at a problem and break it down into distinct steps

when you have a set of steps you should then be able to identify which algorithm or data structure is best for the task

at hand this concept is called algorithmic thinking and it's something we're going

to try and cultivate together as we work through our content lastly learning about algorithms gives

you a deeper understanding about complexity and efficiency in programming having a better sense of how your code

will perform in different situations is something that you'll always want to develop in hone

algorithmic thinking is why algorithms also come up in big tech interviews interviewers don't care as much that you

are able to write a specific algorithm in code but more about the fact that you can break a seemingly insurmountable

problem into distinct components and identify the right tools to solve each distinct component

and that is what we plan on doing in this course though we're going to focus on some of the tools and concepts you'll

need to be aware of before we can dive into the topic of algorithms if you're ready let's get started

hey again in this video we're going to do something unusual we're going to play a game and by we i mean me and my two

friends here brittany and john this game is really simple and you may have played it before it goes something

like this i'm going to think of a number between 1 and 10 and they have to guess what the number is easy right

when they guess a number i'll tell them if their guess is too high or too low the winner is the one with the fewest

tries all right john let's start with you i'm thinking of a number between one and ten what is it

between you and me the answer is three uh quick question does the range include one and ten

that is a really good question so what john did right there was to establish the bounds of our problem

no solution works on every problem and an important part of algorithmic thinking is to clearly define what the

problem set is and clarify what values count as inputs yeah 1 and ten are both included is it

one too low is it two too low is it three correct okay so that was an easy one it took

john three tries to get the answer let's switch over to brittany and play another round using the same number as the

answer okay brittany i'm thinking of a number between 1 and 10 inclusive so both 1 and 10 are in the range what

number am i thinking of is it 5 too high 2 too low

is it 3 correct all right so what we had there was two very different ways of playing the same game

somehow with even such a simple game we saw different approaches to figuring out a solution

to go back to algorithmic thinking for a second this means that with any given problem there's no one best solution

instead what we should try and figure out is what solution works better for the current problem

in this first pass at the game they both took the same amount of turns to find the answer so it's not obvious who has

the better approach and that's mostly because the game was easy let's try this one more time now this

time the answer is 10. all right john you first is it one too low is it two still too low is it three

too low is it four too low is it five still too low is it six too low is it seven too low is it eight low is it nine

do low is it ten correct you got it okay so now same thing but with britney this time

is it five too low eight too low is it nine still too low it's ten

all right so here we start to see a difference between their strategies when the answer was three they both took the

same number of turns this is important when the number was larger but not that much larger 10 in this case we start to

see that britney strategy did better she took four tries while john took 10. we've played two rounds so far and we've

seen a different set of results based on the number they were looking for if you look at john's way of doing

things then the answer being 10 the round we just played is his worst case scenario he will take the maximum number

of turns 10 to guess it when we picked a random number like three it was hard to differentiate which

strategy was better because they both performed exactly the same but in john's worst case scenario a

clear winner in terms of strategy emerges in terms of algorithmic thinking we're

starting to get a sense that the specific value they're searching for may not matter as much as where that value

lies in the range that they've been given identifying this helps us understand our

problem better let's do this again for a range of numbers from one to one hundred we'll

start by picking five as an answer to trick them okay so this time we're going to run

through the exercise again this time from one to one hundred and both one and one hundred are included is it one at

this point without even having to run through it we can guess how many tries john is going to take since he starts at

one and keeps going he's going to take five tries as we're about to see is it five cool correct

okay now for brittany's turn is it 50 too high is it 25 still too high

is it 13 too high is it seven too high is it four too low

is it six too high is it five correct let's evaluate john took five tries brittany on the other hand takes seven

tries so john wins this round but again in determining whose strategy is preferred there's no clear winner right

now what this tells us is that it's not particularly useful to look at the easy

answers where we arrive at the number fairly quickly because it's at the start of the range

instead let's try one where we know john is going to do poorly let's look at his worst case scenario where the answer is

100 and see how britney performs in such a scenario okay john let's do this one more time

one through 100 again is it one we can fast forward this scene because well we know what happens john

takes 100 tries hi brittany you're up is it 50 too low is it 75 too low 88 too

low 94 too low is it 97 too low 99 too low

100. okay so that took brittney seven turns again and this time she is the clear

winner if you compare their individual performances for the same number set you'll see that britney's approach

leaves john's in the dust when the answer was five so right around the start of the range john took five

turns but when the answer was 100 right at the end of the range he took 100 tries it took him 20 times the amount of

tries to get that answer compared to britney on the other hand if you compare

britney's efforts when the number was 5 she took seven tries but when the number was 100 she took the same amount of

tries this is pretty impressive if we pretend that the number of tries is the number of seconds it takes britney and

john to run through their attempts this is a good estimate for how fast their solutions are

ok we've done this a couple times and brittany and john are getting tired let's take a break in the next video

we'll talk about the point of this exercise in the last video we ran through an

exercise where i had some of my co-workers guess what number i was thinking so was the point of that

exercise you might be thinking hey i thought i was here to learn about algorithms

the exercise we just did was an example of a real life situation you will run into when building websites apps and

writing code both approaches taken by john and brittany to find the number i was

thinking of are examples of searching for a value it might be weird to think that there's

more than one way to search but as you saw in the game the speed at which the result was obtained differed between

john and brittany think about this problem from the perspective of a company like facebook

at the time of this recording facebook has 2.19 billion active users let's say you're traveling in a

different country and meet someone you want to add on facebook you go into the search bar and type out

this person's name if we simplify how the facebook app works it has to search across these 2.19

billion records and find the person you are looking for the speed at which you find this person

really matters imagine what kind of experience it would be if when you search for a friend facebook put up a

spinning activity indicator and said come back in a couple hours i don't think we'd use facebook as much

if that was the case from the company's perspective working on making search as fast as possible

using different strategies really matters now i said that the two strategies

britney and john used were examples of search more specifically these are search

algorithms the strategy john took where he started at the beginning of the range and just

counted one number after the other is a type of search called linear search it is also called sequential search

which is a better description of how it works or even simple search since it really is quite simple

but what makes his approach an algorithm as opposed to just looking for something remember we said that an algorithm is a

set of steps or instructions to complete a task linear search is a search algorithm and

we can define it like this we start at the beginning of the list or the range of values

then we compare the current value to the target if the current value is the target value

that we're looking for we're done if it's not we'll move on sequentially to the next value in the list and then

repeat step 2. if we reach the end of the list then the target value is not in the list

this definition has nothing to do with programming and in fact you can use it in the real world for example

i could tell you to walk into a bookstore and find me a particular book and one of the ways you could do it is

using the linear search algorithm you could start at the front of the bookstore and read the cover or the

spine of every book to check that it matches the book that you're looking for if it doesn't you go to the next book

and repeat until you find it or run out of books what makes this an algorithm is the

specificity of how it is defined in contrast to just jumping into a problem and solving it as we go along an

algorithm follows a certain set of guidelines and we use the same steps to solve the problem each time we face it

an important first step to defining the algorithm isn't the algorithm itself but the problem we're trying to solve

our first guideline is that an algorithm must have a clear problem statement it's pretty hard to define an

instruction set when you don't have a clear idea of what problem you're trying to solve

in defining the problem we need to specify how the input is defined and what the output looks like when the

algorithm has done its job for linear search the input can be generally described as a series of

values and the output is a value matching the one we're looking for right now we're trying to stay away from

anything code related so this problem statement definition is pretty generic but once we get to code we can actually

tighten this up once we have a problem an algorithm is a set of steps that solves this problem

given that the next guideline is that an algorithm definition must contain a specific set of instructions in a

particular order we really need to be clear about the order in which these instructions are

executed taking our simple definition of linear search if i switched up the order and

said move sequentially to the next value before specifying that first comparison step if the first value were the target

one our algorithm wouldn't find it because we moved to the second value before comparing

now you might think okay that's just an avoidable mistake and kind of common sense

the thing is computers don't know any of that and just do exactly as we tell them so specific order is really important

the third guideline is that each step in our algorithm definition must not be a complex one and needs to be explicitly

clear what i mean by that is that you shouldn't be able to break down any of the steps into further into additional

subtasks each step needs to be a distinct one we can't define linear search as search

until you find this value because that can be interpreted in many ways and further broken down into many more steps

it's not clear next and this one might seem obvious but algorithms should produce a result

if it didn't how would we know whether the algorithm works or not to be able to verify that our algorithm

works correctly we need a result now when using a search algorithm the end result can actually be nothing which

indicates that the value wasn't found but that's perfectly fine there are several ways to represent

nothing in code and as long as the algorithm can produce some results we can understand its behavior

the last guideline is that the algorithm should actually complete and cannot take an infinite amount of time

if we let john loose in the world's largest library and asked him to find a novel we have no way of knowing whether

he succeeded or not unless he came back to us with a result okay so quick recap what makes an

algorithm an algorithm and not just something you do one it needs to have a clearly defined

problem statement input and output when using linear search the input needs to be just a series of values but to

actually use brittany's strategy there's one additional precondition so to speak if you think about her strategy it

required that the numbers be sorted in ascending order this means that where the input for john

is just a series of values to solve the problem the input to brittany's algorithm needs to be a sorted series of

values so clearly defined problem statement clearly defined input and clearly

defined output second the steps in the algorithm need to be in a very specific order

the steps also need to be distinct you should not be able to break it down into further subtasks

next the algorithm should produce a result and finally the algorithm should

complete in a finite amount of time these guidelines not only help us define what an algorithm is but also helps us

verify that the algorithm is correct executing the steps in an algorithm for a given input must result in the same

output every time if in the game i played the answer was 50 every time then every single time

john must take 50 turns to find out that the answer is 50. if somehow he takes 50 turns in one round then 30 the next and

we technically don't have a correct algorithm consistent results for the same set of

values is how we know that the algorithm is correct i should stress that we're not going to

be designing any algorithms on our own and we'll start off and spend most of our time learning the tried and true

algorithms that are known to efficiently solve problems the reason for talking about what makes

for a good algorithm though is that the same set of guidelines makes for good algorithmic thinking which is one of the

most important skills we want to cultivate when we encounter a problem before

rushing in and thinking about solutions what we want to do is work through the guidelines

first we break down the problem into any possible number of smaller problems where each problem can be clearly

defined in terms of an input and an output now that we know how to generally define

an algorithm let's talk about what it means to have a good algorithm an important thing to keep in mind is

that there's no one single way to measure whether an algorithm is the right solution because it is all about

context earlier we touched on two concepts correctness and efficiency

let's define correctness more clearly because before we can evaluate an algorithm on efficiency we need to

ensure its correctness before we define our algorithms we start by defining our problem

in the definition of that problem we have a clearly defined input satisfying any preconditions and a clearly defined

output an algorithm is deemed correct if on every run of the algorithm against all

possible values in the input data we always get the output we expect part of correctness means that for any

possible input the algorithm should always terminate or end if these two are not true then our

algorithm isn't correct if you were to pick up an algorithm's textbook and look up correctness you

will run into a bunch of mathematical theory this is because traditionally algorithm correctness is proved by

mathematical induction which is a form of reasoning used in mathematics to verify that a statement is correct

this approach involves writing what is called a specification and a correctness proof

we won't be going into that in this course proof through induction is an important

part of designing algorithms but we're confident that you can understand algorithms both in terms of how and when

to use them without getting into the math so if you pick up a textbook and feel daunted don't worry i do too but we

can still figure things out without it all right so once we have a correct algorithm we can start to talk about how

efficient an algorithm is remember that this efficiency ultimately matters because they help us solve

problems faster and deliver a better end user experience in a variety of fields for example algorithms are used in the

sequencing of dna and more efficient sequencing algorithms allow us to research and understand diseases better

and faster but let's not get ahead of ourselves we'll start simple by evaluating john's linear search

algorithm in terms of its efficiency first what do we mean by efficiency there are two measures of efficiency

when it comes to algorithms time and space sounds really cool and very sci-fi huh

efficiency measured by time something you'll hear called time complexity is a measure of how long it takes the

algorithm to run time complexity can be understood generally outside the context of code

and computers because how long it takes to complete a job is a universal measure of efficiency the less time you take the

more efficient you are the second measure of efficiency is called space complexity and this is

pretty computer specific it deals with the amount of memory taken up on the computer

good algorithms need to balance between these two measures to be useful for example you can have a blazingly

fast algorithm but it might not matter if the algorithm consumes more memory than you have available

both of these concepts time and space complexity are measured using the same metric but it is a very technical

sounding metric so let's build up to it slowly and start simple a few videos ago i played a game with

brittany and john where they tried to guess the number i was thinking of effectively they were searching for a

value so how do we figure out how efficient each algorithm is and which algorithm

was more suited to our purposes if we consider the number of tries they took to guess or search for the value as

an indicator of the time they take to run through the exercise this is a good indicator of how long the algorithm runs

for a given set of values this measurement is called the running time of an algorithm and we'll use it to

define time complexity in the game we play it four rounds let's recap those here focusing on john's

performance in round one we had 10 values the target was 3 and john took 3 turns

in round 2 we had 10 values the target was 10 and john took 10 turns in round 3 we had 100 values the target

was john took five tries and finally in round four when the target was 100 given

100 values john took 100 tries on paper it's hard to gauge anything about this performance

when it comes to anything with numbers though i like to put it up on a graph and compare visually

on the vertical or y-axis let's measure the number of tries it took john to guess the answer or the running time of

the algorithm on the horizontal or x-axis what do we put for each turn we have a number of values

as well as a target value we could plot the target value on the horizontal axis but that leaves some

context and meaning behind it's far more impressive that john took five tries when the range went up to 100 then when

he took three tries for a maximum of 10 values we could plot the maximum range of

values but then we're leaving out the other half of the picture there are data points however that

satisfy both requirements if we only plot the values where the target the number john was looking for

was the same as the maximum range of values we have a data point that includes both the size of the data set

as well as his effort there's an additional benefit to this approach as well

there are three ways we can measure how well john does or in general how well any algorithm does

first we can check how well john does in the best case or good scenarios from the perspective of his strategy

in the range of 100 values the answer being a low number like three at the start of the range is a good scenario he

can guess it fairly quickly one is his best case scenario or we could check how well he does on

average we could run this game a bunch of times and average out the running time

this would give us a much better picture of john's performance over time but our estimates would be too high if the value

he was searching for was at the start of the range or far too low if it was at the end of the range

let's imagine a scenario where facebook naively implements linear search when finding friends

they looked at the latest u.s census saw that 50 of names start with the letters a through j which is the first 40 of the

alphabet and thought okay on average linear search serves us well but what about the rest of those whose

names start with the letter after j in the alphabet searching for my name would take longer

than the average and much longer for someone whose name starts with the letter z

so while measuring the run time of an algorithm on average might seem like a good strategy it won't necessarily

provide an accurate picture by picking the maximum in the range we're measuring how our algorithm does

in the worst case scenario analyzing the worst case scenario is quite useful because it indicates that

the algorithm will never perform worse than we expect there's no room for surprises

back to our graph we're going to plot the number of tries a proxy for running time of the algorithm against the number

of values in the range which will shorten to n n here also represents john's worst case

scenario when n is 10 he takes 10 turns when n is 100 he takes 100 turns but these two values alone are

insufficient to really get any sort of visual understanding moreover it's not realistic

john may take a long time to work through 100 numbers but a computer can do that in no time

to evaluate the performance of linear search in the context of a computer we should probably throw some harder and

larger ranges of values at it the nice thing is by evaluating a worst case scenario we don't actually have to

do that work we know what the result will be for a given value of n using linear search it

will take n tries to find the value in the worst case scenario so let's add a few values in here to build out this

graph okay so we have a good picture of what this is starting to look like as the

values get really large the running time of the algorithm gets large as well we sort of already knew that

before we dig into this runtime any deeper let's switch tracks and evaluate brittany's work

by having something to compare against it should become easier to build a mental model around time complexity

the algorithm john used linear search seemed familiar to us and you could understand it because it's how most of

us search for things in real life anyway brittany's approach on the other hand got results quickly but it was a bit

harder to understand so let's break it down just like john's approach britney

started with a series of values or a list of numbers as her input where john just started at the beginning

of the list and searched sequentially brittany's strategy is to always start in the middle of the range

from there she asks a comparison question is the number in the middle of the range

equal to the answer she's looking for and if it's not is it greater than or less than the answer

if it's greater than she can eliminate all the values less than the one she's currently evaluating if it's lesser than

the answer she can eliminate all the values greater than the one she's currently evaluating

with the range of values that she's left over with she repeats this process until she arrives at the answer

let's visualize how she did this by looking at round three in round three the number of values in

the range was 100 the answer was 5. the bar here represents the range of values one of the left 100 at the right

and this pointer represents the value britney chooses to evaluate so she starts in the middle at 50. she

asks is it equal to the answer i say it's too high so this tells her that the value she is evaluating is greater than

our target value which means there's no point in searching any of the values to the right of 50 that is values greater

than 50 in this range so she can discard those values altogether she only has to consider values from 1

to 50 now the beauty of this strategy and the reason why britney was able to find the

answer in such few turns is that with every value she evaluates she can discard half of the current range

on her second turn she picks the value in the middle of the current range which is 25. she asks the same question i say

that the value is too high again and this tells her that she can discard everything greater than 25 and the range

of values drops from 1 to 25. again she evaluates the number in the middle roughly so that'd be 13 here i

tell her this is still too high she discards the values greater moves to value at 7 which is still too high

then she moves to 4 which is now too low she can discard everything less than 4 which leaves the numbers 4 through 7.

here she picked 6 which was too high which only leaves one value 5. this seems like a lot of work but being

able to get rid of half the values with each turn is what makes this algorithm much more efficient

now there's one subtlety to using binary search and you might have caught on to this

for this search method to work as we've mentioned the values need to be sorted with linear search it doesn't matter if

the values are sorted since a linear search algorithm just progresses sequentially checking every element in

the list if the target value exists in the list it will be fouled but let's say this range of values 100 was unsorted

britney would start at the middle with something like 14 and ask if this value was too low or too high i say it's too

high so she discards everything less than 14. now this example starts to fall apart

here because well britney knows what numbers are less than 14 and greater than one she doesn't need an actual

range of values to solve this a computer however does need that remember search algorithms are run

against lists containing all sorts of data it's not always just a range of values containing numbers

in a real use case of binary search which we're going to implement in a bit the algorithm wouldn't return the target

value because we already know that it's a search algorithm so we're providing something to search for instead what it

returns is the position in the list that the target occupies without the list being sorted a binary search algorithm

would discard all the values to the left of 14 which over here could include the position where our target value is

eventually we'd get a result back saying the target value doesn't exist in the list which is inaccurate

earlier when defining linear simple search i said that the input was a list of values and the output was the target

value or more specifically the position of the target value in the list so with binary search there's also that

precondition the input list must be sorted so let's formally define binary search

first the input a sorted list of values the output the position in the list of the target value we're searching for or

some sort of values indicate that the target does not exist in the list remember our guidelines for defining an

algorithm let me put those up again really quick the steps in the algorithm need to be in

a specific order the steps also need to be very distinct the algorithms should produce a result

and finally the algorithm should complete in a finite amount of time let's use those to define this algorithm

step one we determine the middle position of the sorted list step two we compare the element in the

middle position to the target element step three if the elements match we return the middle position and end

if they don't match in step 4 we check whether the element in the middle position is smaller than the target

element if it is then we go back to step 2 with a new list that goes from the middle

position of the current list to the end of the current list in step five if the element in the

middle position is greater than the target element then again we go back to step two with a new list that goes from

the start of the current list to the middle position of the current list we repeat this process until the target

element is found or until a sub list contains only one element if that single element sublist does not

match the target element then we end the algorithm indicating that the element does not exist in the list

okay so that is the magic behind how britney managed to solve the round much faster

in the next video let's talk about the efficiency of binary search [Music]

we have a vague understanding that britney's approach is better in most cases but just like with linear search

it helps to visualize this much like we did with linear search when determining the efficiency of an

algorithm and remember we're still only looking at efficiency in terms of time time complexity as it's called we always

want to evaluate how the algorithm performs in the worst case scenario now you might be thinking well that doesn't

seem fair because given a series of data if the target value we're searching for is somewhere near the front of the list

then linear search may perform just as well if not slightly better than binary search and that is totally true

remember a crucial part of learning algorithms is understanding what works better in a given context

when measuring efficiency though we always use the worst case scenarios as a benchmark because remember it can never

perform worse than the worst case let's plot these values on the graph we started earlier with the number of tris

or the runtime of the algorithm on the y axis and the maximum number of values in the series or n on the horizontal axis

to represent the worst case scenario we have two data points when n equals 10 britney took four tries using binary

search and when n equals 100 it took seven tries but even side by side these data points

are sort of meaningless remember that while there is quite a difference between the run time of

linear search and binary search at an n value of 100 for a computer that shouldn't matter

what we should check out is how the algorithm performs at levels of n that might actually slow a computer down

as n grows larger and larger how do these algorithms compare to one another let's add that to the graph

okay now a picture starts to emerge as n gets really large the performance of these two algorithms differs

significantly the difference is kind of staggering actually

even with the simple game we saw that binary search was better but now we have a much more complete idea of how much

better for example when n is 1000 the runtime of linear search measured by the number

of operations or turns is also 1000. for binary search it takes just 10 operations

now let's look at what happens when we increase n by factor of 10 at 10 000 linear search takes 10 000

operations while binary search takes 14 operations and increased by a factor of 10 in

binary search only needs four more operations to find a value if we increase it again by a factor of

10 once more to an n value of 100 000 binary search takes only 17 operations it is blazing fast

what we've done here is plotted on a graph how the algorithm performs as the input set it is working on increases

in other words we've plotted the growth rate of the algorithm also known as the order of growth

different algorithms grow at different rates and by evaluating their growth rates we get a much better picture of

their performance because we know how the algorithm will hold up as n grows larger

this is so important in fact it is the standard way of evaluating an algorithm and brings us to a concept called big o

you might have heard this word thrown about and if you found it confusing don't worry we've already built up a

definition in the past few videos we just need to bring it all together let's start with a common statement

you'll see in studies on algorithms big o is a theoretical definition of the complexity of an algorithm as a function

of the size wow what a mouthful this sounds really intimidating but it's really not let's

break it down big o is a notation used to describe complexity and what i mean by notation

is that it simplifies everything we've talked about down into a single variable an example of complexity written in

terms of big o looks like this as you can see it starts with an uppercase letter o that's why we call it

big o it's literally a big o the o comes from order of magnitude of complexity so that's where we get the

big o from now complexity here refers to the exercise we've been carrying out in measuring efficiency

if it takes brittany 4 tries when n is 10 how long does the algorithm take when n

is 10 million when we use big o for this the variable used which we'll get to distills that

information down so that by reading the variable you get a big picture view without having to run through data

points and graphs just like we did it's important to remember that complexity is relative

when we evaluate the complexity of the binary search algorithm we're doing it relative to other search algorithms not

all algorithms bigo is a useful notation for understanding both time and space

complexity but only when comparing amongst algorithms that solve the same problem

the last bit in that definition of big o is a function of the size and all this means is that big o measures complexity

as the input size grows because it's not important to understand how an algorithm performs in a single data set but in all

possible data sets you will also see big o referred to as the upper bound of the algorithm and

what that means is that big o measures how the algorithm performs in the worst case scenario

so that's all big o is nothing special it's just a notation that condenses the data points and

graphs that we've built up down to one variable okay so what do these variables look like

for john's strategy linear search we say that it has a time complexity of big o and then n so that's again big o with an

n inside parentheses for britney strategy binary search we say that it has a time complexity of big

o of log n that's big o with something called a log and an n inside parentheses now don't worry if you don't understand

that we'll go into that in more detail later on in the course each of these has a special meaning but

it helps to work through all of them to get a big picture view so over the next few videos let's examine what are called

common complexities or common values of big o that you will run into and should internalize

in our discussions of complexity we made one assumption that the algorithm as a whole had a single measure of complexity

that isn't true and we'll get at how we arrive at these measures for the entire algorithm at the end of this exercise

but each step in the algorithm has its own space and time complexity in linear search for example there are

multiple steps and the algorithm goes like this start at the beginning of the list or

range of values compare the current value to the target if the current value is the target value that we're looking

for we're done if it's not we'll move on sequentially to the next value in the list and repeat

step two if we reach the end of the list then the target value is not in the list

let's go back to step two for a second comparing the current value to the target

does the size of the data set matter for this step when we're at step two we're already at

that position in the list and all we're doing is reading the value to make a comparison reading the value is a single

operation and if we were to plot it on a graph of runtime per operations against n it looks like this a straight line

that takes constant time regardless of the size of n since this takes the same amount of time in any given case we say

that the run time is constant time it doesn't change in big o notation we represent this as

big o with a 1 inside parentheses now when i first started learning all this i was really confused as to how to read

this even if it was in my own head should i say big o of one when you see this written you're going

to read this as constant time so reading a value in a list is a constant time operation

this is the most ideal case when it comes to run times because input size does not matter and we know that

regardless of the size of n the algorithm runtime will remain the same the next step up in complexity so to

speak is the situation we encountered with the binary search algorithm traditionally explaining the time

complexity of binary search involves math i'm going to try to do it both with and without

when we played the game using binary search we notice that with every turn we were able to discard half of the data

but there's another pattern that emerges that we didn't explore let's say n equals 10. how long does it

take to find an item at the 10th position of the list we can write this out so we go from 10 to 5 to 8 to 9 and

then down to 10. here it takes us four tries to cut down the list to just one element and find

the value we're looking for let's double the value of n to 20 and see how long it takes for us to find an

item at the 20th position so we start at 20 and then we pick 10 from there we go to 15 17 19 and finally 20.

so here it takes us five tries okay let's double it again so that n is 40 and we try to find the item in the

40th position so when we start at 40 the first midpoint we're going to pick is 20 from

there we go to 30 then 35 37 39 and then 40. notice that every time we double the

value of n the number of operations it takes to reduce the list down to a single element only increases by 1.

there's a mathematical relationship to this pattern and it's called a logarithm of n

you don't really have to know what logarithms truly are but i know that some of you like underlying explainers

so i'll give you a quick one if you've taken algebra classes you may have learned about exponents here's a

quick refresher 2 times 1 equals 2. now this can be written as 2 raised to the first power

because it is our base case two times one is two now two times two is four this can be

written as two raised to the second power because we're multiplying two twice first we multiply two times one

then the result of that times 2. 2 times 2 times 2 is 8 and we can write this as 2 raised to the 3rd power

because we're multiplying 2 3 times in 2 raised to 2 and 2 raised to 3 the 2 and 3 there are called exponents and

they define how the number grows with 2 raised to 3 we start with the base value and multiply itself 3 times

the inverse of an exponent is called a logarithm so if i say log to the base 2 of 8 equals 3 i'm basically saying the

opposite of an exponent instead of saying how many times do i have to multiply this value i'm asking

how many times do i have to divide 8 by two to get the value one this takes three operations

what about the result of log to the base two of sixteen that evaluates to four so why does any of this matter

notice that this is sort of how binary search works log to the base 2 of 16 is 4.

if n was 16 how many triads does it take to get to that last element well we start in the middle at 8 that's

too low so we move to 12 then we move to 14 then to 15 and then to 16 which is 5 tries or log to the base 2 of 16 plus 1.

in general for a given value of n the number of tries it takes to find the worst case scenario

is log of n plus one and because this pattern is overall a logarithmic pattern we say that the

runtime of such algorithms is logarithmic if we plot these data points on our

graph a logarithmic runtime looks like this in big o notation we represent a

logarithmic runtime as big o of log n which is written as big o with log n inside parentheses or even sometimes as

l n n inside parentheses when you see this read it as logarithmic time

as you can see on the graph as n grows really large the number of operations grows very slowly and eventually

flattens out since this line is below the line for a linear runtime which we'll look at in a

second you might often hear algorithms with logarithmic runtimes being called sublinear

logarithmic or sub-linear runtimes are preferred to linear because they're more efficient but in practice linear search

has its own set of advantages which we'll take a look at in the next video next up let's look at the situation we

encountered with the linear search algorithm we saw that in the worst case scenario

whatever the value of n was john took exactly that many tries to find the answer

as in linear search when the number of operations to determine the result in the worst case scenario is at most the

same as n we say that the algorithm runs in linear time

we represent this as big o of n now you can read that as big o of n like i just said or you can say linear time which is

more common when we put that up on a graph against constant time and logarithmic time we

get a line that looks like this any algorithm that sequentially reads the input will have linear time

so remember anytime you know a problem involves reading every item in a list that means a linear run time as you saw

from the game we played brittany's strategy using binary search was clearly better and we can see that on the graph

so if we had the option why would we use linear search which runs in linear time remember that binary search had a

precondition the input set had to be sorted while we won't be looking at sorting

algorithms in this course as you learn more about algorithms you'll find that sorting algorithms have varying

complexities themselves just like search does so we have to do additional work prior to using binary search

for this reason in practice linear search ends up being more performant up to a certain value of n because the

combination of sorting first and then searching using binary search adds up the next common complexity you will hear

about is when an algorithm runs in quadratic time if the word quadratic sounds familiar to you it's because you

might have heard about it in math class quadratic is a word that means an operation raised to the second power or

when something is squared let's say you and your friends are playing a tower defense game and to

start it off you're going to draw a map of the terrain this map is going to be a grid and you

pick a random number to determine how large this grid is let's set n the size of the grid to four

next you need to come up with a list of coordinates so you can place towers and enemies and stuff on this map so how

would we do this if we start out horizontally we'd have coordinate points that go 1 1 1 2 1 3

and 1 4. then you go up one level vertically and we have points 2 1 2 2 2 3 and 2 4.

go up one more and you have the points 3 1 3 2 3 3 and 3 4 and on that last row you have the points 4 1 4 2 4 3 and 4 4.

notice that we have a pattern here for each row we take the value and then create a point by adding to that every

column value the range of values go from 1 to the value of n

so we can generally think of it this way for the range of values from 1 to n for each value in that range we create a

point by combining that value with the range of values from 1 to n again doing it this way for each value in the

range of 1 to n we create an n number of values and we end up with 16 points which is also n times n or n squared

this is an algorithm with a quadratic runtime because for any given value of n we carry out n squared number of

operations now i picked a relatively easy so to speak example here because in english at

least we often denote map sizes by height times width so we would call this a 4 by 4 grid which is just another way

of saying 4 squared or n squared in big o notation we would write this as big o of n squared or say that this is

an algorithm with a quadratic runtime many search algorithms have a worst case quadratic runtime which you'll learn

about soon now in addition to quadratic runtimes you may also run into cubic runtimes as

you encounter different algorithms in such an algorithm for a given value of n the algorithm executes n raised to the

third power number of operations these aren't as common as quadratic algorithms though so we won't look at

any examples but i think it's worth mentioning thrown up on our graph quadratic and

cubic runtimes look like this so this is starting to look pretty expensive computationally as they say we

can see here that for small changes in n there's a pretty significant change in the number of operations that we need to

carry out the next worst case runtime we're going to look at is one that's called

quasi-linear and a sort of easier to understand for lack of better word by starting with the big o notation

quasi-linear runtimes are written out as big o of n times log n we learned what log n was right a

logarithmic runtime whereas n grew the number of operations only increased by a small factor with a quasi-linear runtime

what we're saying is that for every value of n we're going to execute a log n number of operations hence the run

time of n times log n so you saw earlier with the quadratic runtime that for each value of n we

conducted n operations it's sort of the same in that as we go through the range of values in n we're executing login

operations in comparison to other runtimes a quasi-linear algorithm has a runtime

that lies somewhere between a linear runtime and a quadratic runtime so where would we expect to see this

kind of runtime in practical use well sorting algorithms is one place you will definitely see it

merge sort for example is a sorting algorithm that has a worst case runtime of big o of n log n

let's take a look at a quick example let's say we start off with a list of numbers that looks like this and we need

to sort it merge sort starts by splitting this list into two lists down the middle

it then takes each sub list and splits that in half down the middle again it keeps doing this until we end up with

a list of just a single number when we're down to single numbers we can do one sort operation and merge these

sub-lists back in the opposite direction the first part of merge sort cuts those lists into sub-lists with half the

numbers this is similar to binary search where each comparison operation cuts down the

range to half the values you know the worst case runtime in binary search is log n so these

splitting operations have the same runtime big o of log n or logarithmic but splitting into half isn't the only

thing we need to do with merge sort we also need to carry out comparison operations so we can sort those values

and if you look at each step of this algorithm we carry out an n number of comparison operations and that brings

the worst case runtime of this algorithm to n times log n also known as quasi linear don't worry if you didn't

understand how merge sort works that wasn't the point of this demonstration we will be covering merge sorts soon in

a future course the run times we've looked at so far are all called polynomial runtimes an

algorithm is considered to have a polynomial runtime if for a given value of n its worst case runtime is in the

form of n raised to the k power where k just means some value so it could be n squared where k equals 2 for a quadratic

runtime n cubed for a cubic runtime and so on all of those are in the form of n raised

to some power anything that is bounded by this and what i mean by that is if we had a

hypothetical line on our graph of n raised to the k power anything that falls under this graph is considered to

have a polynomial runtime algorithms with an upper bound or a runtime with a big o value that is

polynomial are considered efficient algorithms and are likely to be used in practice

now the next class of runtimes that we're going to look at are a runtimes that we don't consider efficient and

these are called exponential runtimes with these runtimes as n increases slightly the number of operations

increases exponentially and as we'll see in a second these algorithms are far too expensive to be used

an exponential runtime is an algorithm with a big o value of some number raised to the nth power

imagine that you wanted to break into a locker that had a padlock on it let's assume you forgot your code

this lock takes a two digit code and the digit for the code ranges from zero to nine

you start by setting the dials to zero and then with the first dial remaining on zero you change the second dial to

one and try and open it if it doesn't work you set it to two then try again you would keep doing this and if you

still haven't succeeded with the second dial set to 9 then you go back to that first dial set it to 1 and start the

second dial over the range of values you'd have to go through is 0 0 to 9 9 which is 100

values this can be generalized as 10 to the second power since there are 10 values

on each dial raised to two dials searching through each individual value until you stumble on the right one is a

strategy called brute force and brute force algorithms have exponential run times

here there are two dials so n is 2 and each dial has 10 values so again we can generalize this algorithm as 10 raised

to n where n represents the number of dials the reason that this algorithm is so

inefficient is because with just one more dial on the lock the number of operations increases significantly

with three dials the number of combinations in the worst case scenario where the correct code is the last digit

in the range is 10 raised to 3 or 1 000 values with an additional wheel it becomes 10

raised to 4 or 10 000 values as n increases the number of operations increases exponentially to a point where

it's unsolvable in a realistic amount of time now you might think well any computer

can crack a four digit numerical lock and that's true because n here is sufficiently small but this is the same

principle that we use for passwords in a typical password field implemented well users are allowed to use letters of

the english alphabet so up to 26 characters numbers from 0 to 9 and a set of special characters of which there can

be around 33 so typically that means each character in a password can be one out of 69

values this means that for a one character password it takes 69 to the nth power so

1 which equals 69 operations in the worst case scenario to figure out the password

just increasing n to 2 increases the number of operations needed to guess the password to 69 squared or

4761 operations now usually on a secure website there isn't really a limit but in general

passwords are limited to around 20 characters in length with each character being a possible 69

values and there being 20 characters the number of operations needed to guess the password in the worst case scenario is

69 raised to the 20th power or approximately 6 followed by 36 zeros number of operations

an intel cpu with five cores can carry out roughly about 65 000 million instructions per second that's a funny