00:04there are usually many ways a problem
00:07can be tackled when writing computer
00:09programs often there is no best approach
00:12although programmers are often
00:14considering trade-offs between
00:15processing time memory or disk
00:17requirements and the readability of an
00:20algorithm however sometimes when there's
00:24more than one approach that could be
00:25taken some algorithms are better than
00:28others in terms of how efficiently they
00:30execute in this first video of a
00:32two-part series we explore how
00:34algorithms can be measured a method of
00:37determining efficiency and how we can
00:39use a notation to express this so let's
00:43take a very simplistic piece of code and
00:46consider how we could measure it so here
00:49in this algorithm we're reading in three
00:52names into an array called names here we
00:56can see there are seven lines of code
00:58that need to be executed so we could
01:00state that there are seven steps to
01:02solve the algorithm it has a complexity
01:05of 7 now let's look at a piece of code
01:09that achieves the same result but this
01:11time with a simple for loop here we can
01:15see there are seven lines of code again
01:17but this time three of them are part of
01:19a loop so we could express the
01:23complexity of the algorithm as three
01:26lines plus three lines plus one line or
01:30three plus three plus one you probably
01:34appreciate by now that we use loops
01:36where possible because it keeps the
01:38program very manageable in terms of the
01:40number of variables and the number of
01:42lines of code they give us a significant
01:45advantage because it makes a program
01:47scalable in other words we could
01:49increase the value of n and it would
01:52have no effect on the number of lines of
01:54code but the so called time complexity
01:56has increased for example let's assume
02:00we wanted to read in 30 names instead of
02:02three all we need to do is change the
02:05value of n in this program from three to
02:08thirty and it would still work without
02:10any additional lines of code and like
02:13the first example above that we looked
02:18number n is pretty arbitrary as long as
02:21you have sufficient memory and could be
02:23any value therefore we're better
02:25expressing our algorithm in terms of
02:28three plus three n plus one that means
02:32three lines of code plus three lines of
02:35code that's execute n number of times
02:38depending on the value of n plus one
02:40line of code the console dot write line
02:42at the end in fact we would probably
02:47write the program like this to give the
02:48user the maximum flexibility since we
02:51were already using an array so here
02:54we're asking the user how many students
02:56do they want to enter before reserving
02:58the memory and then entering that number
03:01of students into the array so in terms
03:04of complexity we can represent this as
03:07four lines of code plus three lines of
03:10code executed n times depending on the
03:12number of students plus one line of code
03:15or four plus three n plus one so a
03:20common misconception here is that
03:22complexity is about how difficult the
03:24algorithm is to write that's not true
03:27there are very simple algorithms that
03:30GCSE or a level students would be
03:32capable of including this one complexity
03:35or time efficiency is about how many
03:38steps are required to complete the
03:40algorithm another misconception is that
03:43complexity is a measure of processing
03:45time although clearly related to
03:47complexity that's not strictly true
03:49either a four gigahertz processor is
03:52clearly going to execute code more
03:54quickly than a 1 gigahertz processor but
03:57the number of steps taken in an
03:58algorithm of the same there's also user
04:01input involved in this algorithm so
04:03actually the time to complete is
04:05entirely dependent on how quickly the
04:07user makes the inputs when considering
04:10efficiency we're looking at the number
04:13of steps to be taken called the time
04:15complexity and the memory requirements
04:17known as the space complexity you could
04:20have two different algorithms programmed
04:22in two different ways
04:23requiring no input and executing on the
04:26same processor architecture they're
04:28likely to have different time and space
04:31even though they achieved the same task
04:34so the interesting thing to consider
04:36when we express the complexity of an
04:38algorithm is that not all parts are
04:40equal in our last example 4 + 3 n plus 1
04:45it's really only the 3n part that is
04:48significant that is the part of the
04:50calculation that has the most impact if
04:53N is a thousand then 3n is three times a
04:57thousand which equals three thousand so
05:01the numbers four and one really have no
05:03overall impact on the complexity we
05:06always think about scaling up an
05:08algorithm and not scaling it down
05:11therefore 4 + 3 n + 1 can actually be
05:15represented simply as 3 n there are two
05:20simple rules to follow remove all the
05:24terms except for the one with the
05:25largest factor or exponent and remove
05:28any constants there is a notation
05:32computer scientists used to express the
05:34complexity of an algorithm named after
05:36the German number theoretician Edmund
05:39Landau he described the scalability of
05:42an algorithm called its order or Oh for
05:45short this is lando symbol and in
05:48computer science we call it Big O so our
05:53algorithm had a complexity of 3 n we can
05:57remove the constant 3 and all we have
06:00left is n this is expressed as Big O n
06:06the algorithm is set to have linear
06:08complexity as the data set grows the
06:12number of lines of code to be executed
06:14grows at the same rate consider a piece
06:19of code that initializes a
06:20two-dimensional array how do we measure
06:23the complexity of this algorithm when
06:25the number of lines to execute is not
06:27determined just by one loop but by a
06:30nested loop 1 loop inside another in
06:33this situation we would refer to it as N
06:36squared or quadratic complexity and for
06:413 dimensional arrays n cubed known as
06:45t-there for expressed in Big O this
06:48would be O N squared there are other
06:53complexities you need to be aware of so
06:55we will summarize these now do some
06:57examples with complexity expressions and
06:59in the next video consider how this
07:02relates to our common algorithms in
07:03computer science with the aim of proving
07:06that one algorithm is often better than
07:08another oh one described constant
07:12complexity it's an algorithm that always
07:15executes in the same time regardless of
07:18the size of the data set these are the
07:20very best algorithms o log n is
07:24logarithmic complexity an algorithm that
07:27halves the data set in each pass is the
07:29opposite to exponential it's efficient
07:32with large data sets these are good
07:34algorithms o n is linear complexity an
07:39algorithm whose performance is
07:41proportional to the size of the data set
07:42and declines as the data set grows it
07:46reduces efficiency with large data sets
07:48these are fair algorithms o N squared is
07:53polynomial complexity an algorithm whose
07:56performance is proportional to the
07:58square of the size of the data set it
08:01significantly reduces efficiency with
08:03increasingly large data sets these are
08:06poor algorithms and Oh 2 n is
08:10exponential complexity an algorithm that
08:13doubles or more with each addition to
08:16the data set in each pass it's the
08:18opposite to logarithmic it's inefficient
08:21and extremely poor algorithms that
08:23should be avoided so let's consider some
08:27examples of expressing the complexity of
08:29algorithms here we have 3n squared plus
08:334 n plus 2 and remember we can remove
08:36all the terms except for the one with
08:38the highest exponent that leaves us with
08:423n squared we can remove the constant
08:46that leaves us with N squared or Oh N
08:50squared in Big O notation this is an
08:53algorithm with polynomial complexity or
08:56quadratic complexity
08:58it is relatively poor so let's have a
09:02look at another example here we've got N
09:05squared plus six n cubed plus two n plus
09:10one so following the rules we remove all
09:14the terms except for the one with the
09:16largest factor or exponent so in this
09:19case we're going to keep six and cubed
09:22because it's the expression that has the
09:24largest impact on the algorithm when we
09:28remove the constant we get left with n
09:30cubed or cubic complexity so in Big O
09:35notation this is o n cubed polynomial
09:39the algorithm is poor here's another
09:43example two n to the power four plus n
09:48minus one so again applying the rules
09:51we're looking for the factor that has
09:55the most significant impact on the
09:57algorithm and in this case it's going to
10:00be two n to the power four we can now
10:03remove any constants and that leaves us
10:06with n to the power four or o n to the
10:10power four it's polynomial complexity
10:14again okay let's just do one more
10:17example here we've got twelve plus six n
10:21plus three plus four n so applying the
10:25rules we're going to look for the term
10:28that has the largest factor on the
10:31algorithm and here we'd say it would be
10:346n so we can remove all the other parts
10:38of the expression we can remove the
10:40constant and we get left with n so Big O
10:44n it's linear complexity this is a fair
![Welp, Here's what the Fed *Just* Said [Fed FOMC Minutes]](/_next/image?url=https%3A%2F%2Fi.ytimg.com%2Fvi%2Fl8u23oq1E9E%2Fhqdefault.jpg&w=3840&q=75)
