Skip to main content
Loading Explore guides…
Big O Notation Examples · Acedra
Home
Explore
Computer Science
Big O Notation Examples
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
179 segments
Copy
Hide video
0:02
[Music]
0:08
in, this, video, i'm, going, to, explain, to you, big, o, notation, as, well, as, how, to perform, time, complex, the, analysis, on various, algorithms, now, i have, a, ton, of examples, and, i, want, to, make, this, video really, focused, on, going, through different, examples, and, practicing performing, time, complexity, analysis, so if, you're, familiar, with, bigo, notation skip, forward, in, the, video, to, those examples, they'll, be, in, the, video, player
0:29
or, in, the, description, if, you're unfamiliar, with, big, o, notation, then stick, around, for, the, first, few, minutes where, i, give, you, a, conceptual, overview on, the, whiteboard, now, i, will, mention that, i'm, not, going, to, be, covering, other time, complexity, analysis, so, we're, not going, to, be, looking, at, big, theta, big omega, space, complexity, we, are, simply looking, at, big, o, notation, and, in, a second, i'm, going, to, explain, what, that, is
0:50
now, before, we, get, into, it, i, will, mention that, i, do, have, a, course, it's, called programming, expert, teaches, fundamental programming, object-oriented, programming advanced, programming, tons, of, practice questions, tons, of, projects, you, guys, can check, it, out, from, the, link, in, the description, and, use, discount, code, tim with, that, said, let's, go, ahead, and, get into, the, video, all, right, so, i, want, to begin, by, just, discussing, what, big-o
1:10
notation, is, very, generally, and, why, it's important, for, programmers, of, all, types to, actually, understand, this, concept, so big, o, notation, is, essentially, a, tool that, we, use, to, analyze, different algorithms, data, structures, and, just sections, of, code, and, figure, out relatively, how, much, time, they're, going to, take, to, execute, based, on, the approximate, number, of, operations, that need, to, be, completed, in, the, worst, case, i
1:33
understand, that, sounds, a, little, bit confusing, but, the, idea, is, we, want, to, be able, to, look, at, two, different, algorithms and, very, quickly, determine, which, one, is going, to, be, more, efficient, based, on, its big, o, notation, so, big, o, notation, again is, a, tool, we're, using, it, to, compare different, solutions, different, algorithms different, data, structures, the, algorithm is, data, structures, that, have, the, best big-o, notations, are, typically, the, ones
1:54
that, we, prefer, because, they're, going, to be, the, most, efficient, they're, going, to take, the, least, amount, of, system resources, or, they're, at, least, going, to execute, the, fastest, now, big-o, notation is, really, concerned, with, what, happens when, we, scale, our, problem, to, a, very large, size, so, we're, not, really, wondering what's, going, to, happen, when, we, sort, 5 numbers, or, 10, numbers, we're, concerned with, what's, going, to, happen, when, we, sort
2:14
a, million, numbers, if, we're, comparing, say different, sorting, algorithms, or, what happens, when, we, pass, the, worst, case scenario, of, numbers, to, be, sort, so, big annotation, worst, case, scenario, for, very large, inputs, that's, what, we're, focused on, okay, that, is, a, very, general introduction, to, big, o, notation, the reason, it's, important, for, us, to understand, this, is, because, there's, a, lot of, scenarios, where, we, can, write, code
2:36
that, solves, a, problem, but, doesn't, do, it in, an, efficient, manner, and, the, only, way we, know, it's, not, happening, efficiently is, if, we, understand, relatively, how, many operations, this, code, takes, compared, to another, more, optimal, solution, so, this, is our, comparison, method, without, this method, you, really, have, no, way, of understanding, you, know, how, long, your code, is, going, to, take, to, execute, and that, means, that, it, might, work, for, a
2:58
small, input, but, if, you, pass, it, say, a thousand, numbers, or, ten, thousand, numbers or, a, large, list, of, strings, or, whatever the, input, type, is, it, may, take, a, really really, long, time, to, execute, and, may, even be, infeasible, there's, a, lot, of algorithms, that, you, and, me, have, probably both, written, in, the, past, where, if, you fed, them, say, a, million, numbers, they, may actually, take, years, decades, hundreds, of years, to, execute, based, on, how
3:20
inefficient, they, are, and, just, the, math that, goes, on, behind, the, scenes, here anyways, we're, going to, start, looking, at a, ton, of, examples, i'm, going, to, hop, over to, the, whiteboard, and, start, explaining to, you, kind, of, the, theory, behind, big, o and, how, we, find, the, big-o, notation, of specific, algorithms, all, right, so, i'm here, on, the, whiteboard, i'm, going, to, ask you, to, please, not, be, too, intimidated, by the, math, that, you're, already, seeing, it's
3:41
going, to, be, really, simplified, once, i start, going, through, a, few, examples, so, as i, mentioned, before, when, we're, talking about, big, o, notation, to, actually, find the, big, o, notation, or, the, big, o, function that, represents, an, algorithm, or, a, data structure, or, whatever, it, is, we, need, to first, know, how, many, operations, a algorithm, is, going, to, take, okay, so, the first, step, that, we, always, do, when, we're analyzing, something, for, its, big, o
4:03
notation, to, try, to, compare, it, against something, else, is, we, figure, out, the approximate, number, of, operations, that this, algorithm, takes, we're, then, going, to use, those, to, simplify, and, find, the, big, o function, or, the, big, o, notation, okay, so let's, write, a, super, simple, example, here let, me, just, get, clicked, into, this, screen and, we'll, start, going, through so, i'm, going, to, say, total is, equal, to, 0, i'm, going, to, say, 4, i, in, n
4:27
i'm, going, to, explain, what, n, is, in, a second, and, hello, catch, just, decided, to join, me, here, i'm, going, to, say total, plus, equals, i, and, then, i'm, just going, to, print, i okay, so, this, is, my, out, now, the, first thing, to, discuss, here, is, n, you're, going to, see, this, a, lot, n, refers, to, the, size of, our, input, so, as, i, mentioned, before when, we're, talking, about, notation, we're really, concerned, with, what, happens, when we, have, really, large, inputs
4:52
so, n, is, just, a, placeholder, to, represent the, size, of, our, input, and, we, write, our big, o, function, and, the, number, of operations, relative, to, n, so, in, this, case here, if, we're, counting, the, number, of operations, that, are, going, to, occur, we have, one, operation, to, define, the variable, we're, going, to, have, n, loops that's, going, to, happen, n, times, because, n is, the, size, of, our, input, right, so, i'm going, to, say, n, and, then, we, have, two
5:15
operations, happening, inside, of, the, for loop, so, if, this, for, loop, happens, n, times and, we, have, two, operations, we, have, a total, of, two, n, operations, happening, in the, for, loop, so, we're, going, to, say, 2n plus, 1, is, the, number, of, total, operations that, this, algorithm, is, going, to, take because, we, have, 1, here, and, then, n, times 2, 2n, hopefully, that, is, clear, so, what we're, going, to, do, is, we're, going, to
5:37
write, this, as, what's, known, as, our, f, of, n okay, i'm, going, to, start, going, through this, definition, in, a, second, let, me, just erase, this, part, here, and, move, over, the 2n, plus, 1. okay, so, actually, we'll, just, rewrite, it over, here okay, so, f, of, n is, going, to, be, equal, to, 2n, plus, 1, and, f of, n, is, going, to, represent, the, number, of operations, that, our, algorithm, takes so, now, let's, look, at, this, definition, so this, says, that, f, n
6:03
is, equal, to, the, big, o, of, g, of, n so, where, f, is, big, o, of, g, you, can, read, it that, way, if, there, exists, constants capital, n, and, c, so, that, for, all, n greater, than, or, equal, to, uppercase, n this, inequality, is, true, now, it's important, to, note, here, that, c, and capital, n, have, to, be, at, least, one, so, one or, greater, uh, and, we'll, go, through, this example, so, this, makes, a, bit, more, sense so, let, me, just, write, out, this, inequality
6:29
we, have, f, of, n needs, to, be, less, than, or, equal, to, c times, g, of, n, so, just, to, stop, and, explain something, here, g, of, n, is, the, function that, we're, looking, for, which, is, going, to be, the, big, o, function, or, the, big, o notation, of, f, of, n, or, of, our, algorithm okay, g, of, n, is, really, what, tells, us approximately, how, long, this, code, is going, to, take, to, run based, on, the, input, in, this, case, n, okay so, everything, refers, to, n, again, we're
6:56
really, concerned, with, what, happens, as, n gets, to, a, very, very, large, number, so, we need, to, find, something, that, satisfies this, inequality, and, we, want, this, right hand, side, here, to, be, greater, than, or equal, to, n, but, be, as, close, to, n, as possible, the, reason, i'm, saying, that, is because, any, of, you, who, are, kind, of working, this, out, in, your, head, already can, probably, realize, if, i, substitute, in 2n, plus, 1, for, f, of, n, here, and, i, say, less
7:18
than, or, equal, to, c, times, you, can, pick some, very, very, massive, function, maybe something, like, n, to, the, exponent, 4, and well, this, is, going, to, be, true, doesn't actually, matter, what, value, i, pick, for, c it, doesn't, matter, what, value, i, pick, for uppercase, n, this, is, always, going, to, be true, so, i, don't, want, to, just, pick, an arbitrarily, large, function, i, want, to find, a, function, that's, as, close, as possible, to, this, one, right, here, that
7:40
still, makes, this, true okay again, i, know, this, is, confusing, we're going, to, keep, going, through, it, there's just, a, lot, to, get, through, before, you, can really, even, look, at, an, example, so, number of, operations, is, 2n, plus, 1., we, have, f, of 1, f, of, n, is, less, than, or, equal, to, c times, g, of, n, and, that's, going, to, be, for all, values, n, that, are, greater, than uppercase, n, so, there's, kind, of, two things, that, we, need, to, pick, here, now, let
7:59
me, just, try, to, erase, this, okay, so, let's now, write, the, inequality, again, 2n, plus, 1 less, than, or, equal, to, c, times, g, of, n and, this, is, 4 n, greater, than, or, equal, to, uppercase, n so, there's, three, things, that, we, need, to find, to, prove, this, true, now, what, i'm going, to, do, is, just, randomly, pick, a function, for, g, of, n, and, show, you, how this, works, so, i'm, going, to, say, 2n plus, 1, is, less, than, or, equal, to, c, times
8:24
and, then, the, function, i'm, going, to, pick for, g, of, n is, simply, n, okay, just, the, regular, linear function, i'm, picking, n so, now, that, we, have, this, and, again, this is, going, to, be, for, here, i'm, not, going, to rewrite, that, we, need, to, find, some, c, that makes, this, true, and, if, we, find, some, c that, does, make, it, true, as, well, as, some uppercase, n, then, we, know, that, this, is kind, of, our, big, o, function, that's, what i'm, going, to, be, calling, it
8:45
all, right, so, for, c, we, can, find, this pretty, easily, we, can, just, pick, a, very large, number, right, i, can, pick, a, number like, 10, i, can, pick, a, number, like, even, 3 here, that'll, make, it, true, essentially anything, other, than, 2, or, 1, is, going, to make, this, true, and, remember, c, has, a minimum, value, of, 1., so, if, i, pick, c equals, 3, then, that, gives, me, the inequality, 2n, plus, 1, is, less, than, or equal, to, 3n
9:08
okay, great, and, then, i, need, to, just, find some, value, uppercase, n, where, all, n values, past, that, or, equal, to, it, make this, true, and, really, i, can, actually, pick the, value, 1, for, this, and, it, will, make this, true, right, so, if, i, pick this, so, n, is, equal, to, 1, then, we, can, just plug, in, 1, and, we'll, see, that, this, is always, going, to, be, true, so, when, i, plug this, in, i, get, 3, less, than, or, equal, to, 3
9:29
so, that's, if, 1, is, 4n, and, if, i, were, to plug, in, 2, 3, 4, 5, so, on, and, so, forth you're, going, to, see, that, this, side, here is, always, going, to, be, less, than, or, equal to, or, sorry, greater, than, or, equal, to this now, what, does, that, mean that, means, that, g, of, n, is, the, big, o notation, of, f, n so, i, can, say, f, n, is, equal, to, the, big, o of, n, and, that's, how, you, write, this, say, f of, n, is, equal, to, big, o, of, n, or, the
9:54
algorithm, has, a, time, complexity, of, big, o of, n okay again, i, know, this, is, confusing, but, i've just, showed, you, very, very, quickly, how, we kind, of, use, this, mathematical, definition to, find, a, g, of, n, now, what, does, g, of, n really, mean, well, g, of, n, means, that, as the, input, increases, the, amount, of, time that, our, function, takes, to, execute increases, linearly, okay, increases, on, a straight, line, as, n, increases, in, a, linear
10:19
function, way, the, amount, of, operations increase, so, if, n, is, one, we, have, one operation, if, n, is, two, we, have, two operations, it's, not, telling, us, the, exact number, of, operations, because, we, know that's, two, n, plus, one, it's, telling, us relatively, what, happens, to, the, amount, of time, it, takes, for, us, to, execute, when, the input, value, for, the, function, gets increasingly, large, that's, the, point hopefully, this, is, coming, across, that's
10:42
what, we're, doing, with, big, o, of, n, here, so yes, big, o, of, n, is, actually, less, than, two n, plus, one, that's, fine, we, don't, care about, the, exact, number, of, operations, we care, what, happens, to, the, amount, of, time it, takes, when, the, input, increases, and now, that, we, have, this, function, n, we, know that, it, increases, linearly, the, amount, of time, so, let's, clear, all, of, this and, let's, just, go, through, one, more example, here, and, look, at, some, of, the
11:04
big-o, functions, which, you, can, see, on kind, of, the, right-hand, side, of, my, screen okay, so, let's, say, we, have, a, function here, that, is, something, like two, n, squared plus, n, plus, one, okay, this, is, the, amount of, operations, that, it, takes, we'll, say this, is, f, of, n, should, have, wrote, it, in the, other, way, but, that's, fine, now, i'm going, to, write, the, rest, of, this, in, black here, uh, just, so, you're, aware, okay, so, now
11:25
we, want, to, find, g, of, n, for, this, so, what do, we, do, well, we're, going, to, write, this out, 2n, squared, plus, n, plus, 1, is, less than, or, equal, to, c, times, g, of, n for, n, greater, than, or, equal, to, n, okay, so now, let's, pick, something, for, n or, pick, something, for, g, of, answer, so, 2, n squared plus, n, plus, 1, less, than, or, equal, to, c times, what, if, we, pick, n, now, if, we, pick, n immediately, we're, going, to, see, here, that
11:52
it, doesn't, actually, matter, what, constant we, give, even, if, we, give, a, constant, like a, thousand, when, i, start, passing, really really, large, values, for, n, n, squared, is going, to, exceed, c, times, n, very, quickly right, so, if, i, pass, even, a, huge, value, for n, uh, like, you, know, a, thousand, ten thousand, you're, gonna, see, that, this, side here, is, gonna, be, a, lot, greater, than, this side, here, even, though, i'm, multiplying, it
12:13
by, a, thousand, now, that's, not, something you're, necessarily, gonna, prove, but, you just, need, to, be, able, to, look, at, that, and kind, of, figure, that, out, when, i, have, an, n squared, and, i, have, an, n, over, here doesn't, matter, what, the, constant, is, this is, always, going, to, outgrow, this, side eventually, when, we, get, to, a, very, large number, of, n, so, that, tells, me, that, i cannot, find, some, c, and, i, cannot, find some, n, and, so, n, is, not, going, to, be, a
12:33
valid, function, for, g, of, n, so, now, instead let's, try, n, squared, so, now, if, i, have, n squared, i'm, actually, going, to, be, able, to prove, that, i, can, find, some, constant, c, so to, prove, this, again, i, just, need, to, find some, c, and, i, need, to, find, some, n, so let's, look, for, a, number, for, c, let's, just pick, a, thousand, okay, so, if, i, say c, is, equal, to, a, thousand, now, we, can, plug this, in, so, we're, gonna, say, a, thousand, n
12:56
squared, and, i, don't, know, why, i'm, writing these, in, different, colors, but, i, just, am i'm, gonna, say, two, n, squared, plus, n plus, one now, it, actually, doesn't, really, matter what, value, i, pick, for, uppercase, n, here in, fact, i, can, pick, any, value, and, you're gonna, see, that, we, get uh, the, correct, inequality, here, okay because, i've, picked, a, large, enough number, for, c, now, you, can, make, a, smaller number, of, receipt, it doesn't, matter, what
13:19
number, you're, picking, you're, just picking, that, to, prove, that, this inequality, is, true, so, for, example, if, we plug, in, say, one, right, we, have, two one plus, one, plus, one that's, going, to, give, us, four, and, then this, right, is, going, to, give, us, a thousand, so, this, is, larger, if, we, pick, 2 this, is, going, to, give, us, 4, 000, this, is going, to, be, a, much, smaller, number, so you're, going, to, see, that, this, side, is
13:39
going, to, be, greater, so, there, we, go, we now, know, that, the, function, here, is, going to, be, n, squared, so, what, we, can, do, is, we can, write f, of, n, is, equal, to, big, o, of, n, squared now, you, might, start, be, starting, to realize, a, pattern, here, and, the, pattern is, you, can, essentially, look, at, the largest, term, when, you, have, things, being multiplied, together, and, understand, that that, is, going, to, be, what, the, big, o
14:03
function, is, now, there's, a, few, tricks, and i, have, to, go, through, a, bunch, of, them, but the, point, is, here, when, we, have, something like, 2n, squared, plus, n, plus, 1, if, my function, g, of, n, is, simply, n, squared, i'm going, to, be, able, to, find, a, large, enough constant, that, it, doesn't, matter, what, the other, terms, are, here, it's, always, going to, be, greater, than, this, so, let, me, just stop, here, for, one, second, go, through, this
14:22
example, again, and, make, sure, it's, clear because, i, get, this, is, confusing, and, this is, something, that, you, have, to, look, at, a bunch, of, times, before, really, starts, to actually, make, any, sense, so, i, have, 2n squared, plus, n, plus, 1, that's, the, number of, operations, that, my, algorithm, takes now, i'm, trying, to, find, a, simplified function, that, is, going, to, give, me, a general, concept, of, what, happens, to, the amount, of, time, or, the, amount, of
14:44
operations, required, from, this, algorithm as, the, input, grows, very, very, very, large so, again, we're, thinking, of, really, large values, of, n, so, when, the, values, of, n, grow really, large, what's, going, to, happen, is this, term, right, here, is, going, to, be dictating, the, number, of, operations, that are, occurring, if, you, pick, a, value, even something, simple, like, 10, right, the, 2 times, n, squared, gives, you, 200, the, n gives, you, 10, and, the, 1, gives, you, 1., so
15:09
these, become, increasingly, less, important the, n, plus, 1, as, n, squared, gets, larger and, larger, and, the, same, thing, happens with, this, 2, here, this, becomes increasingly, less, important, as, n, squared gets, larger, and, larger, and, larger, right that's, really, the, point, here, as, n, gets larger, all, of, the, constants, that, we, have here, n, 1, and, 2, are, going, to, become, less important, now, the, n, is, not, a, constant, i know, but, it, still, becomes, less, important
15:34
because, n, squared, is, much, much, larger than, n, that's, what, we're, looking, at, so what, we, do, is, we, get, the, bigger, notation of, n, squared, because, this, is, the, term that, most, accurately, represents, what happens, to, the, amount, of, output, or, i guess, the, time, to, execute, our, function as, the, input, increases and, again, the, way, we, did, that, is, we're using, the, math, here, to, prove, this, i'm going, to, show, you, a, bunch, of, shortcuts
15:56
so, you, don't, have, to, do, this, math, every time, but, it's, important, just, to, see, kind of, how, this, works, so, you, understand, the math, that, goes, behind, this, and, how, you prove you, know, that, your, bigger, notation, is actually, correct, okay, so, now, let's, just look, at, a, few, more, functions, and, we're going, to, do, them, in, a, really, fast, way and, i'm, going, to, show, you, a, few shortcuts, that, are, going, to, make, this
16:13
seem, really, easy, so, let's, say, we, have, f of, n is, equal, to, 3, and, let's, go, with, n, cubed plus, n, squared, plus, and, then, we're, going to, go, uh, oops, let's, go, like, this log, base, 2, of, n okay, so, notice, these, are, all, pluses right, so, i have, 3n, squared, plus, n squared, plus, log, base, 2, of, n now, a, few, shortcuts, that, you, can, keep, in mind, here, is, whenever, you, have, terms that, are, being, added, together, so
16:40
additive, terms, you, can, essentially, cross out, and, remove, every, single, term, and constant, that, is, not, the, largest, term that, you, have, in, the, expression, so, again the, reason, that, you, can, do, this, is because, as, n, increases, and, reaches infinity n, cubed, is, going, to, dictate, the, amount of, operations, that, this, is, going, to, take let's, just, plug, in, a, value, and, have, a look, at, it, right, all, right, so, let's, just
17:02
plug, in, 10, here, and, see, what, we, get, so we're, gonna, have, i, guess, three, times, a thousand plus, this, is, going, to, be, a, hundred, plus approximately, six, point, six, so, if, we look, at, this, we're, gonna, see these, terms, right, even, the, three, become increasingly, less, important, as, n, gets large, and, n, isn't, even, that, large, n, is ten, imagine, what, happens, now, when, n, is ten, thousand, ten, million, the, n, cubed really, carries, the, number, of, operations
17:28
and, so, we, don't, care, about, these, ones right, here, and, we, can, cross, them, off when, it, comes, to, our, big-o, notation, now to, be, able, to, actually, cross, these, off you, can, do, a, bit, of, math, to, kind, of prove, that, you, can, cross, them, off, so what, i'm, going, to, say, here, is, let's assume, that, n, squared, and, log, base, 2, of n, is, equal, to, n, cubed, so, the, reason, i can, assume, that, is, because, n, cubed, is greater, than, n, squared, let's, assume, that
17:51
n, squared, is, equal, to, n, cubed, now, i, know this, is, not, sound, math, but, just, assume that, n, squared, is, equal, to, n, cubed, if, it is, then, what, i, can, do, is, change, all, my, n squared, terms, to, n, cubed, so, if, i, change n, squared, here, 2n, cubed, which, is, larger than, it, so, it's, vowel, for, me, to do, that because, i'm, adding, something, in, that's larger, than, n, squared, and, i, change, my log, base, 2, of, n, to, the, same, thing, n
18:14
cubed, what, you, see, here, is, we, end, up, now if, we, factor, this, we, get, 5, n, cubed, now again, the, 5, is, a, constant, we, don't, care about, the, constant, because, we, don't, need to, know, the, exact, number, of, operations we, just, want, to, have, the, function, that tells, us, what, happens, as, the, input, gets larger, so, n, cubed, is, that, function, so, we simply, strip, off, the, 5, and, we, say, that the, bigger, notation, here, is, n, cubed
18:36
that's, the, way, that, we, do, this, so, if, you take, every, single, other, term, that, you're adding, it's, very, important, that, you realize, we're, adding, these, terms, here and, you, say, okay, well, if, it's, smaller than, n, cubed, let's, assume, it's, n, cubed now, if, we, add, all, of, these, together, and not, factor, so, i, said, factor, four, if, you add, all, of, them, together, we, get, 5n, cubed we, know, we, don't, care, about, the constants, because, we're, just, looking, for
18:55
a, function, to, give, us the, relative, amount, of, operations, then what, we, can, do, is, cross, off, the, constant which, would, have, been, 5, and, we're, left with, n, cubed okay, so, that's, one, example, let's, now look, at, another, example, that, has, to, do with multiplying, terms, so, let's, now, say, we have, something, like, 3n, and, we're, going to, multiply, this, by, the, log, base, 2, of and, then, this, will, be, n, squared okay, so, this, is, actually, what, we, have
19:20
now, what, we, want, to, do, is, simplify, this and, find, g, of, n, so, we, can, find, the, big, o notation, so, for, this, function, here, the first, thing, that, we, know, we, can, do, is remove, the, constants, again, we, can, remove them, because, we, don't, care, about constant, values, we, only, care, about, a function, based, on, the, input, that, tells us, what, happens, to, the, number, of operations, or, the, expected, kind, of running, time, of, the, algorithm, based, on
19:39
the, size, of, the, input, so, we, can, remove the, constant, so, we, remove, the, constant, 3 and, that, leaves, us, with, n, multiplied, by log, base, 2 of, n, squared, okay, now, we, don't, really know, how, to, handle, this, n, squared, inside of, here, and, i'm, going, to, show, you, how, we can, simplify, this, even, more, you, could technically, say, that, this, is, the, big, o notation, right, now, we, can, get, even simpler, we, can, take, this, 2, out, based, on
20:01
using, exponent, rules, i'm, not, going, to derive, these, rules, for, you, i, assume, most of, you, probably, know, this, already, at least, if, you're, in, high, school, let, me write, log, properly we're, going, to, be, able, to, take, the, 2, out right, before, the, log and, then, we, can, put, this, here, now, again the, reason, we, take, the, 2, out, is, because whenever, we, have, something, to, the exponent, inside, of, a, logarithm, that exponent, we, can, simply, put, as, a
20:22
multiplication, to, whatever, the, logarithm is, of, the, base, of, that, number and, so, that's, what, i'm, doing, so, i'm saying, 2, log, base, 2, of, n, i, can, take, the 2, out, now, the, 2, is, what, a, constant, we don't, care, about, the, constant, so, i, can remove, the, constant, okay, so, now, if, we continue, i, get, n, and, then, i, have, log base, 2, of, n, now, can, i, simplify, this anymore, no, i, cannot, i, cannot, simplify because, we, are, multiplying, these, terms
20:47
not, adding, them, if, we, were, adding, the terms, together, i, could, remove, the, log base, 2, of, n, because, it's, smaller, than, n but, i, cannot, in, any, way, here, find, a, way to, actually, write, this, as, a, constant multiply, by, n, like, previously, if, i, had, n plus, and, then, i, had, log, base, 2, of, n, i can, say, that, since, log, base, 2, of, n, is smaller, than, n, i, can, write, this, as, n plus, n, that, gives, me, 2n, and, then, i, can
21:10
cross, out, 2, but, here, since, we're multiplying, the, terms, together, i, don't have, a, way, to, do, that, and, so, i, can't simply, remove, the, log, base, 2., okay, if you, wanted, the, math, version, of, that that's, why, it, also, makes, sense, here since, we, have, two, factors, being multiplied, they, both, really, affect, how much, time, this, is, taking, so, we, need, to keep, n, log, base, 2, of, n, around okay now, that, we've, looked, at, that, let's, just
21:30
have, a, look, at, what's, on, the, right-hand side, of, my, screen, and, then, let's, get into, some, some, examples, because, i'm, sure a lot, of, you, are, tired, of, this, math so, on, the, right-hand, side, of, my, screen here, we, have, the, big-o, complexity, chart now, let's, just, see, if, we, can, make, this bigger so, that, we, can, take, up, the, full, screen with, it, nice, okay, so, this, is, the, chart now, it, actually, is, pretty, good, i, don't
21:48
really, need, to, explain, it, too, much, but it, simply, shows, you, the, big, o, functions and, which, ones, are, better, than, each other, because, once, you, find, the, big, o notation, that's, great, but, you, need, to know, which, functions, are, better, than other, functions, in, terms, of, their complexity, now, we've, already, looked, at log, of, n log, of, n, is, great, that, means, that essentially, as, the, input, increases, the number, of, operations, we, need, to, do, is, on
22:09
a, logarithmic, basic, basis, which, means it's, getting, smaller, and, smaller, when log, is, equal, to, a, hundred, we, have, six when, log, is, equal, to, uh, 128, we, have seven, when, log, is, equal, to, 256, uh, we have, eight, right so, on, and, so, forth, now, i, might, have, been messing, those, up, a, little, bit, you, get the, point, as, we, get, to, a, really, really large, number, it, stays, really, small, when we, have, a, logarithmic, time, complexity
22:32
then, we, have, a, constant, time, complexity o, of, one, this, means, that, there's actually, nothing, based, on, the, input, this would, be, like, printing, a, number, or, you know, checking, if, a, number, is, odd, or, even performing, a, modulus, this, is, a, constant time, operation, this, isn't, something, that requires, the, input, so, if, it, doesn't matter, to, the, input, at, all, it, only, ever takes, 100, steps, or, 50, steps, or, a thousand, steps, a, constant, number, of
22:54
steps, then, we, have, o1, a, constant, time o, n, this, is, linear, this, is, a, fair, or good, time, complex, if, you, have, a, linear time, complexity, usually, that's, pretty good, it, means, your, algorithm's, time scales, with, the, input, so, as, the, input increases, the, amount, of, operations, uh increase, relatively, at, the, same, amount if, we, have, 10, inputs, we, have, you, know about, 10, operations, if, we, have, 20 operations, or, 20, inputs, we, have, 20
23:18
operations, now, it, might, actually, be, 100 operations, or, 200, operations, but, that's fine, because, it's, happening, linearly, not exponentially or, any, of, the, other, complexities, that we're, going, to, look, at okay, continuing, with, n, log, n, now, n, log, n is, kind, of, a, middle, ground, here, as, you can, see, we're, multiplying, a, linear, time complexity, by, a, logarithmic, so, it's, not horrible, it's, not, as, bad, as, something
23:38
like, n, squared, but, it, is, you, know, fair it's, going, to, take, a, long, period, of, time if, we, have, a, lot, of, inputs, again, all, of these, are, time, estimates, used, to, be compared, against, each, other, we're, not looking, at, an, exact, amount, of, operations or, exact, amount, of, time, so, n, log, n, fair time, complexity, it, is, better, or, sorry worse, than, a, big, o, of, n okay, now, we, have, n, squared, n, squared, is a, horrible, time, complexity, that, means
24:01
that, we, increase, the, number, of operations, we, need, to, do, exponentially as, n, increases, and, i'm, sure, many, of, you have, looked, at, exponents, before not, very, good, when, n, gets, to, a, large number, say, we, add, 10, we, have, n, squared that, gives, us, 100, already, keeps, getting larger, and, larger, and, larger, then, we have, something, like, 2, to, the, exponent, n now, this, is, even, worse, this, is, a, very very, poor, time, conflict, as, you, can, see
24:23
then, we, have, something, like, n, factorial and, we, have, even, more, complex, time complexities, where, we, have, something like, n, factorial, multiplied, by, 2n plus, m, and, would, be, another, input, i'll talk, about, that, later, but, this, is, the general, graph, so, you, kind, of, need, to memorize, this, graph, it's, pretty, easy, you could, just, plug, in, some, values, and actually, see, which, ones, are, getting larger, faster, if, you, are, unsure, but
24:43
these, are, the, most, important, big, o functions, and, we're, going to, be, using combinations, of, these, functions, when we're, analyzing, the, time, complexity, of the, examples, i'm, about, to, go, through, so i, apologize, i, know, this, was, long, but, i just, wanted, to, try, to, explain, this, as best, as, i, could, hopefully, that, made sense, now, we're, going, to, go, through, 12 examples, and, i'm, going, to, walk, you through, exactly, how, we, solve, them, all
25:02
right, so, we're, moving, on, to, the, first example, here, example, zero, i'm, going, to ask, you, right, now, what, is, the, time complexity, or, big, o, notation, of, this function, think, about, it, pause, the, video if, you, need, to, i'm, about, to, go, in, and explain so, the, answer, here, is, that, this, is constant, time, okay, now, i'll, explain, why it's, constant, time, but, this, is, big, o, of one so, inside, of, here, what, we're, doing, is
25:25
we're, performing, a, constant, number, of operations it, does, not, matter, what, num, is, and, num is, going, to, be, n, right, num, is, n, because that's, our, input, so, whatever, the, size, of num, is, we, represent, that, with, the variable, n, and, it, doesn't, matter, what this, is, it's, always, going, to, take, us approximately, the, same, amount, of, time, to perform, this, calculation, right, the modulus, of, 2, or, the, num, modulus, 2, and
25:47
we're, just, checking, if, this, number, is odd, or, even, that's, what, we're, doing, here so, this, is, a, constant, time, operation fairly, straightforward, now, i, want, to mention, that, if, i, did, something, like, x equals, 1, y, equals, 3, whatever, this, is still, a, constant, time, operation, i, don't write, something, like, o, of, 3, i, just, keep it, at, 0, 1, which, means, we're, going, to, do the, same, amount, of, steps, no, matter, what n, is, no, matter, what, the, size, of, our
26:08
input, is, and, as, we, go, through, these, next examples, you're, going, to, see, that, i've labeled, inputs, different, values you, know, numbers, strings, whatever you, still, want, to, represent, them, using, n n, is, the, length, of, your, input, or, the size, of, your, input, in, every, single situation, okay, so, let's, now, go, to example, one example, one, we've, seen, this, example, kind of, already, i've, total, equal, zero, for number, in, nums, total, plus, equals, number
26:34
return, total, pause, the, video, what, is, the big, o, notation, of, this, example, or, of this, algorithm, right, here okay, so, the, answer, as, i'm, sure, many, of you, have, gotten, and, probably, fairly quickly, is, big, o, of, n, now, n, is representing, the, number, of, numbers, that we, have, in, nums, so, the, size, of, our, input now, what, we, do, here, to, calculate, this, is exactly, what, we, did, in, that, first example, that, i, showed, you, we, have, a
26:58
variable, this, takes, one, one, operation right we, have, a, for, loop, this, is, going, to, take n, it, takes, n, because, the, number, of numbers is, n, right, so, this, for, loop, runs, n, times we're, doing, one, operation, so, what, we, end up, getting, here, at, the, end, you, could count, this, as, an, operation, if, you, want as, well, is, something, like n, plus, one, or, n, plus, two, whatever, you want, to, write, okay, so, we'll, say, it's, n
27:19
plus, 1., if, we, have, n, plus, 1, we, know, that we, can, simply, remove, the, constants, which are, 1, because, as, n, gets, larger, they're not, going, to, matter, and, write, the, big, o notation, as, big, o, of, n okay, so, that's, that, example let's, move, forward, okay, now, this, one, is getting, a, bit, more, complicated now, we, have an, example, where, we, have, a, nested, for loop, so, again, pause, the, video, go, ahead and, read, this, and, it's, going, to, get, even
27:42
more, complicated, as, we, go, on, all, right so, let's, go, line, by, line, we, have, results here, and, results, we're, creating, a, list now, this, list, we, have, a, for, loop, here we've, got, to, look, at, all, of, our, loops okay, and, any, operation, that, could, be looping, and, what, happens, is, we, need, to 4n, right, so, for, underscore, in, range, len of, nums, lenum, nums, really, is, just, n we're, adding, 1, into, the, list, so, this, is
28:03
going, to, take, us, n, to, do, because, we're adding, 1, n, times pretty, straightforward move, on, to, the, next, loop, okay, inside, of this, next, loop, well, how, many, times, does it, take, for, this, loop, to, run, this, loop is, going, to, take, n, times, to, run, because we're, doing, it, for, the, size, of, our, input which, is, n okay, now, we, have, another, for, loop, inside of, this, for, loop, now, that, means, that this, for, loop, needs, to, run, how, many times
28:26
n, times, and, how, long, does, it, take, for the, for, loop, to, run, well, this, for, loop is, looping, through, nums, as, well, and, so that, gives, us n, okay, so, we, have, n, stuff, happening, n times, because, this, for, loop, is, happening now, inside, of, here, we, can, count, the operations, we, could, say, this, is, an operation, this, is, an, operation, and, this is, an, operation, now, remember, we're considering, the, worst, case, so, in, one
28:50
case, when, num1, is, equal, to, num2, we're not, going, to, perform, this, operation however, we, don't, really, care, about, that we're, not, going, to, factor, that, into, our calculations, here, because, this could, happen, right, it's, happening, every time, except, once, so, we're, just, going, to assume, that, this, operation, happens, the end, times, for, this, for hopefully, you, get, what, i'm, saying, but i'm, just, trying, to, get, through, like
29:11
don't, over, complicate, analyzing, the number, of, operations, here, we're, just trying, to, get, a, rough, estimate, and, then we, can, actually, figure, out, what, the, big o, notation, is okay, so, we, have, about, three, operations at, most, we, have, to, perform, a, condition we're, going, to, continue, we, could, count as, an, operation, i'm, going, to, do, a multiplication, we'll, just, sum, all, of those, up, even, though, they're, not, all going, to, happen, together, okay, so, we, say
29:30
approximately, we're, going, to, get, three operations, inside, of, here, then, we're returning, results, okay, that's, another operation, so, we, have, n now, we're, adding, that, because, this, is, it not, inside, the, for, loop, where, it's, the next, line, down, to, n okay, and, then, how, many, times, or how, many, operations, are, going, on, inside of, this, n well, we, have, three, n, so, we're, going, to say, n, and, then, this, is, just, going, to, be
29:53
multiplied, by, 3n, now, i, get, this, a, bit confusing, but, what's, happening, is, this for, loop, is, happening every, single, time, this, for, loop, runs, so we're, doing, this, for, loop, n, times, which means, we're, going, to, have, n times, n, right, two, n's, there, so, that's, n squared, and, then, we're, doing, three operations, inside, of, this, internal, for loop, and, so, what, we, end, up, getting, is three, n, squared, if, we, multiply, these, all
30:16
together, we're, gonna, get, n, plus three, n, squared, and, then, we, have, one more, operation, here, so, we, add, one so, this, is, going, to, be, the, you, know approximate, number, of, operations, that we're, doing, inside, of, this, algorithm, now what, do, we, do, well, we, look, for, the largest, term which, is, n, squared, we, cross, off, all, of our, constants, and, then, whenever, we, have a, variable, we, say, okay, was, this, term smaller, or, larger, than, this, one, well
30:39
it's, smaller, so, if, we, assume, it's, n squared, then, we, could, write, this, as, 2n squared, which, means, i, can, now, get, rid, of that, and, that, means, my, big, o, notation, is going, to, be, n, squared, i, know, i, made, a complete, mess, here, but, this, is, going, to be, n, squared, okay, that's, the, big, o notation, let, me, get, out, of, this, mass let's, look, at, it, here in, the, code, edit, so, we, perform, an, n operation that, happens, okay, then, we, go, inside, of
31:00
here, we, have, an, n, times, n, operation because, we're, doing, this, for, n, times, for this, for, loop, which, happens, n, times, we need, to, multiply, them, together inside, this, for, loop, we're, doing, three things, so, we, have, three, n, squared, that's how, long, all, of, this, takes, to, run, so, we add, that, to, n add, that, to, one, and, we, get, 3n, squared plus, n, plus, 1., we, know, the, other, terms are, smaller, so, we, cross, them, off, and
31:24
that, leaves, us, with, the, big, o, notation of, n, squared okay, so, big, o of, n, to, the, exponent, 2. let's, write, that, there okay, this, is, going, to, start, to, make sense, as, we, go, through, more, examples though, that, was, an, n-squared, algorithm now, we're, moving, on, to, this, one, so, let's look, at, this, now, we, have, two, inputs, here so, it, gets, a, bit, more, complicated, num1s and, nums, 2., now, just, like, we, used, n, to represent, the, size, of, our, first, input
31:45
we're, going, to, use, another, letter, in this, case, m, you, can, use, whatever, you want, but, the, tradition, is, n, and, m, for the, second, input, so, we, have, two, inputs you, got, to, consider, with, the, length, of the, size, of, both, of, the, inputs, how, long does, this, take, n, and, m okay, so, pause, the, video, if, you, need, to and, take, a, guess, and, i'm, going, to, run through, so, again, let's, take, a, full screen, snip, here let's, go full, screen, snip
32:08
and, let's, try, this, okay, so, we, have, nums one, nums, two, so, for, nums, one, can, i change, the, pen, color, here, actually, i think, red, is, fine, we'll, say, this, is, n and, we'll, say, that's, m, okay, results, one operation, for, num, in, nums, one, well, nums one, that's, n, so, this, is, going, to, take how, many, operations, are, we, doing, just one, so, we, can, say, this, whole, thing, just takes, n, time, okay nums, two, this, is, m, right, size, of, that
32:33
input, inside, of, here, how, many, operations are, we, doing, just, quickly, add, them, up doesn't, need, to, be, super, precise, one, two three, operations, okay, so, this, is, going to, be, taking, 3m, time results, that, takes, 1., let's, add, these all, together, because, they're, not, inside of, each, other, so, we, can, just, add, them together, so, we're, going, to, have, 1, plus we'll, add, the, other, one, down, here, so, 1 plus, n, plus, three, m
32:56
okay, now, we, need, to, cross, off, all, the constants, so, we, get, rid, of, one, get, rid of, one, get, rid, of, three, what, does, that leave, us, n, plus, m okay, we, cannot, simplify, this, any, further because, n, and, m, are, going, to, be, two distinct, variables, representing, the, two inputs, that, we, have, to, our, function, so you're, going, to, see, this, a, lot, you, have multiple, inputs, you, need, to, use, a different, variable, to, represent, each
33:18
input, and, then, that, tells, you, the approximate, time, complexity, of, the function, so, again, we're, going, to, write this, as, big, o, of, n, plus, m, now, if, you wanted, to, do, this, really, quickly, all, you would, do, is, look, for, the, loops, that involve, n, and, m, so, we, see, we, have, a, loop here, with, n see, we, have, a, loop, here, with, m, boom, all we, do, n, plus, m, that's, all, we, need, to look, at, now, we, can, look, inside, of, these
33:37
loops, and, try, to, see, if, there's, more looping, if, there's, no, looping, and, it's constant, time, operations, which, all, of these, are, here, then, we, don't, have, to consider, them, we, just, cross, them, off because, they're, constant, every, loop, is going, to, take, the, same, amount, of, time, so we, don't, need, to, consider, it, it's, not based, on, the, size, of, the, input okay, so, o, n, plus, m okay, let's, continue, to, example, four, i
33:57
got, a, ton, of, examples, to, keep, practicing this okay, so, now, we're, doing, a, bunch, of, stuff here, so, let's, again, go, to, the, full screen, snip you, guys, can, pause, the, video, if, you, want and, take, a, guess, at, what, the, time complexity, is okay, so, we, have, example, four, we, take, in a, nested, list, now, the, nested, list, is going, to, be, something, like, this right, there's, going, to, be, a, list inside, of, another, list
34:18
and, this, can, make, it, a, bit, complicated so, when, we're, dealing, with, a, nested, list what, we're, going, to, do, is, assume, that the, list, has, a, height, and, a, width, now, we could, draw, this, in, kind, of, more, of, a square, fashion, but, it, might, be, something like, this okay and, what, we, would, get, here, is, this, would be, the, height, so, the, number, of, lists inside, of, the, list, and, then, the, width would, be, the, number, of, elements, inside
34:41
of, each, list, and, we, would, assume, that would, just, be, the, same, okay, so, we, have height, and, width, and, those, are, the, two variables, that, we're, going, to, use, for the, time, complexity, here, because, we, need to, represent, the, number, of, elements, in the, interior, list, as, well, as, how, many lists, we, have, okay, so, let's, look, at, this we, have, one, operation, i'm, going, to, stop counting, these, now, because, we, don't, need
34:58
to, even, consider, them, in, our, operations we're, going, to, cross, them, out, anyways it's, just, one, single, operation, it's constant, doesn't, matter, we, can, just, stop looking, at, it, because, it's, not, going, to be, based, on, the, size, of, the, input however, we, have, a, for, loop, we, say, 4 inner, list, in, nested, list, well, nested list we're, getting, all, of, the, inner, lists, so how, many, of, those, lists, do, we, have, we have, h, of, those, right, h, nested, lists
35:20
okay, we, could, write, that, lowercase, h doesn't, really, matter then, what, are, we, doing, we're, looping through, the, inner, list, now, the, inner list, is, what, well, it's, going, to, be, w whatever, the, width, is, or, the, number, of elements, in, the, inner, list, so, we're doing, w, here, we're, doing, w, here, because it's, the, same, thing, and, we're, doing, w here so, we, have, h times, three, w, right, so, inside, of, here three, w, operations, times, h so, we, get, h
35:46
and, then, this, is, multiplied by, three, w so, that, gives, us, three, h, w and, what, do, we, do remove, the, constants, and, we, get, h, w, okay so, we, can, write, this, as, run, out, of, space here, big, o, of, h w, and, you, know, we'll, just, make, it uppercase, to, stick, with, what, we, have before, so, the, big, o, of, the, height, times the, width, that's, the, number, of operations, that, we're, doing, that's, our big, o, uh, or, time, complexity, for, this algorithm
36:13
hopefully, that, makes, sense hopefully, i'm, staying, with, you, guys, here you're, staying, with, me, actually, please leave, a, comment, if, it's, starting, to, get super, confusing, obviously, doing, this with, no, one, giving, me, any, feedback, it's a little, bit, difficult, to, know, if, people are, following, or, not, but, i, think, this, is a, decent, explanation, we, have, h, in, our list, so, we, have, h, times, we're, going, to do, this, for, loop, right, here, and, then
36:33
inside, of, the, inner, list, we, have, w elements, right, so, we're, doing, this, for loop, w, times, this, for, loop, w, times, as well, so, we're, doing, 3w, for, every, h, so that's, going, to, be, h, times, 3w, for, the number, of, operations, we, have, a, constant in, there, which, is, 3., we, don't, care, about the, constant, we, remove, it, and, we, get, w times, h great, okay, next, example example, five, now, this, is, a, recursive example, uh, going, to, be, a, bit, more
37:00
difficult, here, what, i, would, recommend you, do, is, try, this, with, a, very, small value, so, try, this, with, number, three, or try, this, with, a, value, 2, and, see, what actually, happens, when, you, give, it, kind of, these, small, values, and, how, many operations, end, up, happening, in, that, case okay, so, i'm, going, to, go, to, the, screen snip, now, and, let's, look, at, this okay so, this, is, a, recursive, example, is actually, a, very, famous, problem, it's, the
37:22
fibonacci, sequence, now, i, will, just, tell you, that, the, big-o, notation, is, 2, to, the exponent, n, but, we, want, to, walk, through why, we're, getting, 2, to, the, exponent, n, so we, need, to, understand, how, this, code actually, works so, we're, going, to, deal, with, a, lot, of recursive, stuff, when, we're, looking, at time, complexity, analysis, and, the important, thing, to, look, at, here, with recursive, functions, is, how, many recursive, function, calls, are, happening
37:45
in, every, step so, we, want, to, figure, out, essentially, how many, times, is, this, function, going, to, run and, then, we, want, to, multiply, that, by, the number, of, operations, occurring, in, the function, that's, how, you, deal, with recursive, function, calls, how, many, times does, the, function, run multiply, that, by, the, number, of operations, inside, of, the, function, now the, first, thing, we're, going, to, look, at here, is, the, operations, in, the, function
38:08
because, that's, the, easiest, to, figure, out so, we, have these, are, constant, time, operations, right so, we, don't, need, to, consider, them, these all, take, constant, time, okay, all, that, so we, can, kind, of, cross, all, those, out, we don't, even, care, about, those, now, this operation, right, here, this, is a, recursive function, call, so, we're, not, going, to consider, that, because, that's, going, to have, to, do, with, how, many, times, the
38:25
function, runs, again, recursive, function call, and, then, we, have, another, constant time, operation, that, we, don't, really, care about, so, if, we're, looking, inside, of, the the, actual, function, itself, we'll, just say, that, the, function, takes, constant time, to, execute, however, how, many, times is, the, function, going, to, run, well, that's based, on, these, recursive, calls, so, once we, figure, that, out, we'll, know, the, time complexity, so, let's, just, do, a, simple
38:47
example, here, with, an, input, of, size, five so, if, we, have, five, then, what, we, need, to do, is, we, need, to, call, the, function, at four, and, at, three, because, we, have, four here, and, three, here, when, n, is, five, okay those, are, the, two, function, calls, we, need to, make, from, four, we're, gonna, have, to make, the, function, call, three, and, two, by the, way, i'm, not, making, these, in, the order, they're, going, to, be, done, i'm, just
39:04
trying, to, write, out, the, whole, tree, from three, we're, going, to, have, to, call, two and, one, okay, because, our, base, cases, are one, and, two, so, whenever, we, hit, one, and two, we're, done, so, done, done, done, from, 3 we're, going, to, have, to, call, 2, and, 1. okay, so, this, is, what, our, tree, looks, like so, what, you, should, be, noticing, here, is that, we're, going, to, end, up, getting, a time, complexity of, 2n, so, the, reason, why, we're, getting, 2n
39:26
here, is, because, for, each, input, to, the function, we're, doing, two, recursive, calls so, if, we, start, at, 5, and, we, do, a, call, to 4, and, we, do, a, call, to, 3, we've, done, two calls, and, then, from, these, numbers, we need, to, do, two, calls, as, well, now, we, are going, to, end, up, doing, less, than, two, n operations, however, this, is, the, best function, we, can, use, to, approximate, how many, operations, are, going, to, occur, in
39:48
this, function, or, in, this, algorithm, so, we have, two, recursive, calls, the, calls, are going, down, by, any, minus, one, and, n, minus two, so, a, constant, value, they're decreasing, by, not, something, like, divided by, 2, or, divided, by, 4, which, would, be, much different, we'll, look, at, that, in, a, second we're, reducing, these, by, a, constant, value so, the, most, amount, of, steps, we're, going to, have, to, do, for, every, input, is, 2, and
40:08
that, means, we're, going, to, have, 2, to, the exponent, and, potential, steps, now, if, you want, to, prove, that, to, yourself, keep expanding, this, tree, look, at, 6, look, at, 7 look, at, 8, look, at, 9, and, you're, going, to see, how, many, operations, you, have, to, do and, how, we, expand, in, this, way, in, an exponential, way, okay, so, 2, to, the exponent, n, is, the, time, complexity, here this, is, kind, of, just, a, complex, do, you
40:26
have, to, be, familiar, with, again, the, way, i determine, this, is, how, many, function calls, i, can, have at, most, now, again, i, will, have, less function, calls, than, this, but, this, is, the most, approximate, function, i, can, use, for the, big-o, notation, so, we, have, big, o, of 2n, all, kinds, of, other, videos, on, the fibonacci, sequence, that, can, probably explain, that, as, well, in, more, depth, so let's, write, the, comment of, big, o of, n, or, sorry, 2, to, the, exponent
40:51
okay, now, let's, go, to, example, six all, right, example, six, so, this, one, we have, lst, and, search, list, actually, let, me go, back, i, don't, know, why, i, keep, keep going, full, screen, here, let's, go and, take, a, snip okay, so, we're, gonna, call, lst, here n, and, this, will, be, m, so, two, different inputs, we, have, two, lists, go, ahead, pause the, video, determine, the, time, complexity okay, so, let's, get, started, here, so, the
41:14
first, thing, we, need, to, do, is, we've, got to, look, at, this, operation, here, now, a, lot of, you, are, going, to, say, that, this, is, a constant, time, operation, it, just, happens in, one, right, we, just, count, this, as, one operation, now, we, cannot, because, what, max actually, does, in, python, is, it, loops through, the, entire, list, and, finds, the maximum, value, so, you've, got, to, be careful, here, whenever, you're, using internal, language, features, like, built-in
41:35
functions, max, min, stuff, like, that, even you, know, slicing, an, array, for, example slicing, a, list, you, need, to, actually consider, what's, happening, on, the, lower level, and, how, long, that's, actually, going to, take, so, if, i, want, to, find, the, maximum number, in, the, list, the, only, way, for, me to, do, that, is, to, search, through, every element, in, the, list, so, if, i, have, a, list i, have, one, two, three, four and, i'm, looking, for, element, two, okay
41:57
yeah, it, only, takes, me, two, steps, to, go through, this, but, i, still, need, to, say that, this, is, going, to, take, me, o, n, time because, if, the, element, 2, was, pushed, to the, very, end, of, the, list, i, would, have, to look, through, every, element, in, the, list to, find, it, so, this, is, where, the, worst case, comes, in, right, when, i'm, searching through, a, list, i, might, find, the, element immediately, or, i, might, find, it, at, the very, end
42:15
so, in, the, worst, case, i, have, to, assume it's, going, to, take, me, n, time, to, find, the element, so, i, say, that, finding, the maximum, element, in, a, list, takes, me, o, n time hopefully, that, is, clear, so, o, n, time, for this, first, operation so, let, me, just, write, an, n, here, okay, so that, takes, n, to, find, the, max then, we're, gonna, look, for, a, value, in, the search, list, so, we're, gonna, say, four value, in, search, list, and, we're, gonna
42:40
check, if, the, maximum, value, is, equal, to the, value, and, return, true, so, this, here this, is, going, to, take, us, m, time now, again, this, might, not, take, us, m, time if, the, maximum, value, is, equal, to, the value, in, the, very, first, value, that, we look, at, we, immediately, return, true, and this, actually, took, us, constant, time, it took, us, one, operation, to, do, this however, if, the, value, that, we're, looking for, isn't, in, this, list, or, it's, one, of
43:03
the, later, elements, in, this, list, it, takes us, m, time, to, look, through, it, so, in, the worst, case, the, element, doesn't, exist, we have, to, loop, through, every, single element, in, the, search, list, just, to, find that, it's, not, there, that, takes, m, time now, that, makes, the, total, time, complexity here, n, plus, m, so, big, o, of, n, plus, m, we, do the, first, operation, which, is, n, looking for, the, maximum, element, in, the, first
43:25
list, and, then, we, search, through, all, of the, elements, in, the, second, list, in, the worst, case, giving, us, big, o, of, n, plus, m all, right, let's, continue uh, example, seven, okay, so, this, one, is, a bit, more, complicated, again, has, to, do with, recursion, uh, pause, the, video, take your, time, and, try, to, guess, what, the, time complexity, is okay, let's, open, up, our, snip, here, and let's, go, through, this, so, for, this, one, it
43:46
is, a, little, bit, tricky, but, we, really want, to, pay, attention, to, this, n, over, 2 here, and, what's, happening, in, this recursive, call, so, previously, when, we, saw recursive, calls, or, when, that, one, example we, saw, it, we, had, a, time, complexity, of two, of the, exponent, n now, the, reason, we, had, that, is, because, we were, calling, two, calls, for, every, single input, right, so, each, input, five, i'm calling, i'm, calling, the, function, twice
44:09
and, i, was, only, reducing, n, by, a, constant amount, i, was, reducing, it, by, two, three four, one, any, constant, amount, that, i'm reducing, it, by, is, going, to, cause, me, to get, something, like, 2n, now, if, i, had, three recursive, calls, i, would, have, got, 3n, if, i had, four, recursive, calls, for, every, input i, would, have, got, 4n, assuming, that, i, was reducing, everything, by, a, constant, value now, here, i'm, only, doing, one, recursive
44:32
call, and, i'm, reducing, this, not, by, a constant, i'm, saying, n, over, 2., so, i'm actually, reducing, it, by n, like, n, is, a, part, of, the, reduction factor, if, that, makes, sense, so, when, i, do something, like, n, over, 2, you, can, see, that i'm, very, quickly, going, to, get, smaller numbers, so, 40, goes, to, 20, 20, goes, to, 10 10, goes, to, 5., 5, goes, to, 2.5, 2.5, let's round, it, goes, to, 1, right, so this, is, how, quickly, we, reduce, from, a
44:57
very, large, number, now, this, is, actually logarithmic, okay, this, gives, us, the, log base, 2, of, n, is, the, time, complex, again i'm, going, to, continue, to, explain, this but, you, need, to, keep, this, in, mind, so, we have, log, base, 2, of, n so, n, is, constantly, being, divided, by, 2. every, time, it, gets, divided, by, 2, that's reducing, in, a, much smaller, end, right, and, so, that, means, we only, are, actually, going, to, do, log, base, 2
45:20
of, n, recursive, calls, or, at, least, that's what, our, time, complexity, is, going, to, be because, that's, how, we're, reducing, n, so again, if, we, start, with, n, equal, to, say 100, then, we're, only, doing, one, recursive call, and, the, next, recursive, call, goes, to 50., then, it, goes, to, 25, right, then, it's going, to, go, to, approximately, 12.5, we're rounding, this, so, it, would, go, to, 13, okay that's, fine, goes, to, 13, we, divide, 13, by, 2
45:43
that's, going, to, give, us, approximately, 7 okay, divide, 7, by, 2, that's, going, to, give us, approximately, 4., divide, that, by, 2 we're, going, to, get, 2, divide, that, by, 2 we're, going, to, get, 1., so, log, base, 2, of, n is, telling, us, how, many, operations because, we're, reducing, by, a, factor, of, 2. i, don't, really, know, if, i, can, explain this, much, better, than, that, if, we, had, a, 3 then, this, would, be, the, log, base, 3, of, n
46:03
okay, not, log, base, 2., the, reason, it's, 2 is, because, that's, what, we're, dividing, by so, really, you, can, just, kind, of, plug, in some, numbers, and, see, how, many, operations it's, actually, going, to, take, when, we're doing, recursive, calls, or, we're, reducing the, number, of, operations, by, dividing, it by, two, we're, dividing, it, by, four dividing, it, by, five, and, n, is, what, we're dividing, it, by, well, that, means, we're going, to, get, some, type, of, logarithmic
46:23
time, complexity, and, the, larger, n, gets the, fewer, amount, of, operations, we're actually, going, to, have, to, be, doing, now that, wasn't, the, most, accurate, way, to, say that, but, you, get, the, point, as, n, gets really, really, large, the, amount, of operations, we, have, to, do, is, not, growing with, the, size, of, n, it's, really, small relative, to, n, when, n, gets, very, large that's, kind, of, what, i, was, trying, to, say okay, so, that's, that, one, so, this, is simply the
46:45
log of, n, okay, and, this, is, log, base, two, of, n i, don't, really, have, a, better, way, to write, that, okay, now, let's, go, to, example eight so, let, me, get, the, snip, here, again, pause the, video, if, you, would, like, to, try, this out, on, your, own so, we're, saying, we're, taking, a, list, of strings, okay, so, these, are going, to, be multiple, strings, inside, of, a, list, we're saying, 4i, string, and, enumerate, strings so, immediately, we're, going, to, say, this
47:09
is, going, to, take, end, time, where, n, is, the number, of, strings, that, we, have, okay, the size, of, our, input, n now, with, strings, though, right, if, we, look at, a, string, like, hello the, number, of, characters, in, a, string, is going, to, dictate, how, long, it, takes, to process, that, string, which, you're, about to, see, here, so, i, have, 4, char, in, string now, string, is, an, individual, string, so there's, not, really, a, good, way, for, me, to
47:31
figure, out, how, many, operations, it's going, to, take, for, me, to, process, a, string because, i, don't, know, the, length, of, the string, so, i, need, to, come, up, with, another variable, here, i'm, going, to, use, the variable, k, and, k, is, going, to, be, the, max length, of, any, string, inside, of, this, list so, i'm, going, to, say, this, is, k now, the, reason, i'm, doing, this, is, because whatever, the, maximum, length, of, a, string is, that's, the, most, number, of, times, that
47:56
this, for, loop, is, going, to, have, to execute, and, i'm, looking, for, the, worst case, scenario, here, so, i, can, approximate all, of, the, other, strings, length, 2k because, k, is, the, longest, length, of, any string, that, i, have, so, that's, the, most amount, of, times, it's, going, to, have, to happen, so, i, say, it's, k now, inside, of, here, what, am, i, doing, i'm saying, if, char, is, in, string, i, for, i, in range, 0, 10, now, some, of, you, may, be
48:16
tempted, to, include, this, as, part, of, your time, complexity, this, is, constant, this takes, 10, steps, every, time, so, since, it always, takes, 10, steps, i, don't, have, to count, it, i, don't, care, about, that, and, i'm not, even, going, to, look, at, this, if statement, okay so, now, we, have, n, okay then, i, have, this, i, have, if, digits greater, than, or, equal, to, length, of string, over, two, strings, i, equals, sorted strings, i, now, the, only, part, that, i'm
48:38
looking, at, here, is, sorted, now, we, should know, that, to, sort, a, list, to, sort, a string, to, sort, anything, the, most efficient, way, we, can, do, this, is, in, n log, n, time, where, this, is, base, 2., now, i completely, butcher, that, so, let, me rewrite, it, and, i'm, also, going, to, write it, in, k, because, that's, what, we're, going to, have, to, use, here, so, we're, going, to say, k, and, then, this, is, going, to, be, log base, 2
49:00
of, k, now, k, is, the, length, of, the, longest string, so, the, most, amount, of, time, it will, take, to, sort, something, here, is, k log, base, 2, of, k now, if, you, don't, know, why, that's, the case, you're, just, going, to, have, to, trust me, here, the, most, efficient, way, to, sort something at, least, a, general, thing, that, you're sorting, not, something, specific, is, k, log base, 2, of, k or, n, log, base, 2, of, n, now, k, is, the longest, length, of, the, string, that, we
49:23
have, we, have, to, use, k, because, we, don't know, how, long, the, string, is, going, to, be so, we, say, whatever, the, maximum, length, is that's, what, we'll, put, here, because, that will, give, us, an, upper, bound, and, give, us the, worst, case, scenario, so, we, have, k, log base, 2, of, k, that's, how, long, this, takes, i know, i, kind, of, butchered, writing, it there, but that's, the, operation, okay, so, now, we've figured, out, our, operations, so, we, have, n
49:42
we, have, k, and then, we, have, k, log, base, 2 of, k so, inside, of, this, for, loop, right, here this, takes k plus and, then, this, is, going, to, be okay, you, know, what, let, me, clear, this because, it's, going, to, be, hard, to, to, do this, okay, so, this, is, going, to, be n multiplied, by, and, then, this, is, going, to be, k plus and, then, k, and, this, will, be, the, log base, 2. okay, now, again, this, is, not, always, going to, happen, right, we're, not, always, going
50:15
to, have, to, sort, but, we, could, always, have to, sort, that's, the, thing, it's, the, worst case, so, since, we, could, always, have, to sort, this, we're, going, to, have, to, factor that, into, our, time, complexity, and, assume we're, always, sorting, it, so, we, have, n which, again, was, this, we, have, k, which, was this, and, then, we, have, the, k, log, base, 2 of, k, which, is, here, so, inside, the, for loop we, have, the, k, plus, k, log, base, 2, of, k
50:35
then, we, have, to, multiply, that, by, n because, we're, going, to, do, that, at, most, n times, now, though, we're, able, to, simplify things, because, we, have, k, plus, k, log, base 2, of, k, you, can, do, the, factoring, here, and you'll, see, that, we'll, get, k, multiplied by, 1, plus, log, base, 2, of, k, which, means, we could, get, rid, of, the, 1, and, so, i, can instead, now, say, it's, going, to, be, n and, then, k and, then, log, of, k, so, this, is, my, time
50:58
complexity, i, can, parenthesize, it, if, i'd like, but, it's, going, to, be, n, times, k, log base, 2, of, k all, right, there, we, go so, that, is, that, time, complexity i'm, going, to, start, going, a, little, bit faster, just, because, we've, looked, at these, a, lot, already, so, it's, going, to, be n, k log, 2, k and, we, can, write, it, like, this, if, we'd like uh, and, maybe, even, do, another, parenthesis although, it, doesn't, really, matter, all
51:23
right, so, now, let's, move, on, to, example nine, okay, this, one's, a, complicated, one so, please, pause, the, video, and, try, to figure, it, out, but, let, me, explain, it, now we, have, two, keys, or, we, have, two dictionaries, sorry, so, i'm, going, to, say these, are, n, and, m, in, terms, of, their, size and, these, dictionaries, are, going, to, have key, uh, or, sorry, string, keys, okay, or, keys that, are, strings, whatever, so, i, say, keys
51:42
one, and, keys, two, and, i'm, sorting, a, bunch of, strings, now, to, sort, the, strings, we're just, going, to, say, that, this, takes, n, and then, this, is, going, to, be, log, base, 2, of, n time, and, then, for, this, one, since, we're sorting, dictionary, 2, which, is, m, we're going, to, say, this, is, m log, base, 2, of, m okay, now, we, have, our, process, now, we, have keys, 1, plus, keys, 2., now, there's, going, to be, n, keys, in, keys, 1, and, m, keys, in, keys
52:04
two, so, this, is, going, to, take, us, n, plus, m time, to, create, that, make, a, set, constant time, operation, now, we, have, this, while loop, now, what, we, need, to, do, here, for, the while, loop, is, figure, out, how, many, times it's, gonna, run, and, then, how, much, or, how much, time, it, takes, sorry inside, of, the, while, loop, uh, to, perform operations so, how, many, operations, are, we, doing, in the, for, loop, how, many, times, is, the, uh
52:24
sorry, how, many, operations, are, we, doing in, the, while, loop, how, many, times, does the wall, loop, run, multiply, them, together there, we, go, we, have, the, time, for, the while so, let's, start, by, figuring, out, the operations, in, the, well so, we, have, element, equals, process, dot pop, zero, now, popping, from, zero immediately, tells, me, that, this, is, going to, be, a, big, o, of, n, operation, or, in, this case, n, plus, m, so, let, me, show, you, what, i
52:45
mean, if, we, have, a, list, and, let's, just say, we, have, four, elements if, i, pop, the, first, element, and, remove this, element, what, that, means, i, have, to do, is, shift, every, element, over, one position okay, to, restore, its, position, in, the, list there, is, data, structures, that, allow, you to, do, this, in, constant, time, however, the data, structure, list, in, python, does, not so, this, is, an, o, n, time, operation, where, n is, the, number, of, elements, in, the, list
53:09
now, since, the, number, of, elements, in, our process, list, is, going, to, be, at, most, n plus, m, that, means, we're, gonna, have, to take, if, i, could, freaking, erase, all, this stuff, here, n, plus, m, time, to, perform these, pops, so, i'm, gonna, say okay, let's, get, this, properly, n, plus, m now, again, we're, not, always, to, have, n plus, m, elements, in, the, process, list because, we're, removing, elements, that's what, we're, doing, in, here, but, the, most, we
53:32
will, have, when, we, start, is, n, plus, m so, we, need, to, write, that, here, as, how much, time, this, operation, will, take, in the, worst, case continuing, we, add, something, to, the results, list, don't, care, about, that, we're checking, the, length, don't, care, about that, now, we, have, process, dot, append, now what, we're, doing, is, appending, a, string but, we're, removing, the, last, character, of the, string, so, what, you, need, to, realize
53:54
is, happening, here, is, we, are, processing every, single, string, key, in, both, of, the lists, and, we're, going, to, keep, adding, the string, itself, back, into, the, process, list until, it, has, no, elements, left, in, it, so for, every, string, that, we, process, we're going, to, be, adding, that, string, minus, its last, character, back, to, the, process, list whatever, the, length, of, the, string, times is, so, if, i, have, a, basic, string, like, high
54:18
then, what, i, do, is, i, strip, off, this, last character, but, i, add, h, back, to, the process, list, which, means, it, needs, to, be processed, again, causing, the, while, loop to, happen, another, time so, again, more, complicated, algorithm, here but, i, wanted, to, show, you, how, you, come, up with, these, time, complexities, so, since that's, the, case, now, what, i, need, to, do, is say, okay, well, the, while, loop, is, going, to take, the, existing, process, time, right, so
54:40
n, plus, m, but, this, is, all, going, to, be multiplied, by, k, where, k, is, the, length, of the, longest, string, so, the, most, amount, of times, that, one, single, element, is, going to, be, reinserted, into, process, is, k because, that, is, well, the, length, of, the longest, string, right, so, if, i, have, a string, the, longest, string, is, five, well it's, going, to, take, me, five, reinsertions it's, really, going, to, be, four, but, still we're, going, to, have, to, process, that
55:03
element, five, times, by, adding, it, back into, the, process, list, so, i, need, to multiply, the, maximum, length, of, the string, by, n, plus, m, which, is, how, many elements, are, already, in, there, because for, each, of, those, elements, they, could, be inserted, a, maximum, of, k, times again, i, know, we're, getting, into, the weeds, here, it's, getting, complicated, but i, wanted, to, give, you, some, advanced examples, because, this, is, stuff, that
55:24
you're, going, to, have, to, learn, at, some point, in, time, so, n, plus, m, multiplied, by k, is, how, long, this, loop, is, taken, so, now what, we, need, to, factor, in, here, is, n, plus m, multiplied, by, k, going, to, be, more, or less, than, n, times, log, base, 2, of, n, and, m times, log, base, 2, of, m, because, now, we have, to, add, these, operations, together, so really, what, we're, going, to, have, is, n then, we're, going, to, have, log, base, 2, of, n
55:47
then, we're, going, to, add, that, to, m of, log, base, 2, of, m, then, we, have, this operation, which, is, n, plus, m, now, n, plus, m we, know, is, going, to, be, less, than, n, plus m, times, k, so, we, can, simply, remove, that from, our, operation, here, and, then, we're going, to, have, n plus, m multiplied, by, k now, we, actually, do, not, know, if, n, plus, m times, k, is, going, to, be, more, or, less, than n, log, base, 2, n, and, m, log, base, 2, m, so, we
56:14
need, to, keep, them, in, so, this, would, be our, total, time, complexity, here, okay, n log, base, 2, n, plus, m, log, base, 2, m, plus, n times, n, times, k, and, then, you, would, write after, this, what, each, of, these, variables mean, m, is, the, number, of, keys, in dictionary, 1, m, number, of, keys, in dictionary, two, and, k, the, length, of, the longest, string, out, of, dictionary, one, or dictionary, two, okay, again, i, know, really complicated, one, probably, not, one, that
56:38
you're, going, to, get, on, like, a, computer science, exam, but, it's, possible, so, i figured, we'd, go, through, this, example here, okay, let's, look, at, example, 10. now, example, 10, again, we're, getting, into more, complicated, ones, only, got, three left, here, let's, take, a, snip pause, the, video, and, give, it, a, go, okay, so actually, we're, going, to, skip, example, 10. i, was, just, going, through, it, and, it's, way too, complicated, to, even, try, to, explain
56:58
in, this, video, so, if, you, guys, want, to guess, the, answer, you, can, in, the, comments down, below, um, anyways, we're, just, going to, move, on, to, 11, because, it's, a, bit simpler, i, don't, want, to, overwhelm, you guys, too, much, so, let's, just, understand this, code, before, we, proceed, any, further we, have, sum, to, the, end, empty, list, count equals, zero, four, i, in, range, the, len, of nums, okay, we're, looping, through, getting
57:17
one, number, then, we're, saying, sum, to, the end, out, of, pen, zero, so, this, is, going, to approach, n then, we're, looping, through, all, of, the numbers, past, this, number, in, our, list okay, because, i, plus, 1, is, the, start, of our, for, loop, range, up, to, the, len, of, nums so, that's, n, right okay, then, what, we're, doing, is, saying, sum to, the, ni, plus, equals, num2 don't, have, to, worry, too, much, about, the addition, we, have, another, for, loop, in
57:40
here, that, is, going, to, loop, through, all of, the, elements, in, sum, to, the, end, so whatever, the, current, length, of, this, list is, that's, how, many, times, this, is happening then, we're, printing, out, our, count, which is, just, how, many, times, this, for, loop, has happened, in, total so, you, can, read, this, and, understand, a bit, more, i, know, i, didn't, really necessarily, explain, it, the, point, is, this sum, to, the, end, list, is, going, to, contain
57:59
the, sum, of, all, of, the, numbers, in, the list, past, the, current, number not, including, the, current, number until, we, get, to, the, end, of, list, that's kind, of, what, it's, doing, so, if, we, have like, one two three, four, then, the, result, here, is, going to, be, whatever, two, plus, three, plus, four is, so, nine, and, then, whatever, three, plus four, is, which, is, seven, then, whatever four, is, which, is, four, and, then, zero okay, that's, what, the, result, is, going, to
58:23
be, because, we, sum, these, three, then, we sum, these, two, then, we, sum, this, one, and place, those, in, the, appropriate, positions in, the, list, and, then, we, would, sum, the last, element, which, which, would, be, zero so, we, place, zero, at, the, end, okay, let's just, get, rid, of, those, though that's, what, this, code, is, doing, okay, so now, that, we, understand, that let, us, continue, and, do, the, time complexity, so, we're, going, to, say, this, is n
58:44
all, right, so, that, means, this, happens, n times, and, then, here, what's, going, to happen, is, this, is, going, to, happen, n times, then, n, minus, 1, times, then, n, minus 2, then, n, minus, 3, as, i, increases, now, if you, actually, look, at, the, value, of, this sequence, you'll, see, that, it, approaches, n squared, so, we, can, simply, say, that, all, of these, added, together, is, n, squared okay which, means, that, we, can, just, kind, of write, this
59:08
as, it, takes, n, times, okay, we, don't, need to, factor, in, all, the, minus, ones, or, minus two, minus, three, so, on, and, so, forth, now continuing, we, have, another, for, loop, now this, for, loop, is, happening, whatever, the length, of, sum, to, the, end, is, so, it's going, to, happen, first, one, time, because that'll, be, the, length, when, i, equals, one then, it, will, happen, two, times, then, three then, four, all, the, way, until, it, gets, to, n
59:30
so, similar, to, how, we, had, n, minus, 1, n minus, 2 and, minus, 3 here, that's, exactly, what, we, have, in, the reverse, order, so, we, know, that, we, can just, say, this, is, going, to, take, n, as, well because, 1, plus, 2, plus, 3, plus, 4, up, to, n approaches, n, squared again, i, don't, want, to, derive, all, the math, here, but, i'm, going, to, write, that this, takes, n so, we, have, n, multiplied, by, n, multiplied by, n, and, that's, all, that, we're, doing
59:55
inside, of, here, which, is, going, to, give, us an, n, cubed, time, algorithm, so, this, for loop, happens, n, times since, inside, of, here, this, for, loop happens, n, times, we, get, n, cubed, so, that's the, time, complexity, big, o, of, n, cubed great, let's, move, on, to, the, last, example here, okay, another, complex, example, pause the, video, take, a, guess, let's, go, through the, time, complexity right, now okay, so, i'm, just, going, to, tell, you, the
1:00:22
time, complexity, here, is, n, factorial, now if, you're, unfamiliar, with, the, factorial obviously, you, would, not, have, guessed this, but, a, factorial, is, the, following, so if, i, have, something, like, four, factorial it, is, four, times, three, times, two, times one, if, i, had, three, factorial, that's three, times, two, times, one okay, that's, factor, so, we, see, these, in time, complexities, and, a, factorial, is, one of, the, worst, time, complexities, that, we
1:00:45
can, have, refer, to, that, graph, i, showed earlier, if, you, want, to, see, exactly, where it, ranks, i, believe, it's, actually, the worst, that, was, on, that, graph so, n, factorial, is, this, time, complexity but, how, do, we, determine, well, this, is recursive, so, we're, going to, have, to, find how, many, times, this, recursive, function runs, and, then, multiply, that, by, how, much work, is, being, done okay so we, have, n, work, being, done, inside, the
1:01:07
forward, you, know, before, we, do, that, let's look, at, the, recursive, calls, so, we, say, if n, is, equal, to, one, return, one, total equals, zero four, underscore, in, range, n, total, plus equals, example, 12, n, minus, one, so, let's try, this, with, an, input, of, three, if, we try, this, with, an, input, of, three, let's say, n, is, currently, equal, to, three, what happens, is, total, is, equal, to, zero, we're saying, four, i, in, range n, and, then, we're, going, to, call, example
1:01:31
12, with, n, minus, one, how, many, times, we call, this, three, times, okay, we, call, it, n times, or, whatever, the, input, to, the function, was, that's, how, many, recursive calls, we, do, so, we, have, one, two, three recursive, calls, all, to, the, same, value which, is, n, minus, one, which, is, two okay, so, there, we, go, now, what, happens, is we, come, to, the, function, and, now, our input, is, two, it's, not, one, so, we, continue so, we're, looping, through, two, and, then
1:01:54
we're, doing, this, how, many, times, whatever n, is, we're, gonna, now, have, two, recursive calls, uh, with, n, being uh, less, than, one, okay, so, we're, gonna, say one, one one, one, and, one, one, now, this, is, going, to look, very, similar, to, the, to, the, exponent n, except, what, you're, going, to, realize is, that, the, levels, in, each, tree, or, the, i guess, width, of, each, section, of, the, tree increases, as, the, input, increases, so, if, i
1:02:19
have, four, i, have, one, two, three, four right, so, let's, say, i, have, three, levels here, well, now, what, i'm, doing, is, i'm saying, okay, i'm, gonna, have, three, levels and, i'm, gonna, multiply, that, by, however many, levels, this, one's, gonna, have, and this, is, gonna, have, how, many, levels, is gonna, have, two, so, that, gives, me, 3 times, 2, levels, then, how, many, levels, this one, have, it, has, 1., this, is, a, factorial that's, what, the, tree, looks, like, now
1:02:41
again, i, know, this, is, confusing, i, know, a lot, of, you, are, going, to, be, lost, at, this point, but, this, is, the, factorial algorithm, and, if, you, look, at, this, and, i punch, in, a, number, say, like, uh, i, guess what's, the, factorial, of, 5, i, believe, it's 120, we'll, get, 120, meaning, we, had, to, do 120, operations, because, that's, the, way that, we've, calculated, them, so, that's what, i, was, trying, to, illustrate, here with, the, factorial, let's, just, look, at
1:03:02
one, more, higher, tree, level, of, four, so you, can, really, see, kind, of, how, this works, so, if, we, have, an, input, of, four here, what, happens, is, we, get four, calls, okay, four, recursive, calls that, all, go, now, to, recursive, calls, of three, and, then, we, get, one, two, three, one two, three, one, two, three, one, two, three then, we, have, two, two, two, two, two, two okay, i'm, gonna, write, a, bunch, of, these here okay, and, then, we, have, one, two, one, two
1:03:29
one, two, one, two, and, if, you, count, how many, of, these, we, actually, have, how, many base, cases, we, hit, we're, going, to, be hitting, whatever, n, factorial, base, cases is, okay, that's, how, many, base, cases, in the, recursion, that, we, hit, this, is, n factorial now, what, we, can, say is, that, theoretically, we're, going, to have, an, upper, bound, of, 2, times, n factorial, recursive, calls, in, total, so, we hit, the, base, case, n, factorial, times, but
1:03:55
we're, going, to, have, in, total, two, times, n factorial, because, to, be, able, to, hit, the base, case, we, had, to, do, all, of, the, other calls, above, now, since, we, have, a, constant we, remove, the, two, and, that, gives, us, n factorial, for, the, time, complexity, of, our algorithm, again hard, to, explain, this, in, much, more, depth than, this, for, some, of, these, things, you kind, of, just, get, it, or, you, don't, and, you have, to, look, at, a, ton, of, different
1:04:16
examples, to, really, see, how, this, works understand, factorials, understand, math maybe, i'm, just, not, the, best, at, teaching it, definitely, open, to, your, comments below, but, that's, really, the, best, that, i can, kind, of, explain, how, the, factorial works, here we, start, with, four and, then, four four, we're, doing, four, fact, uh, four recursive, calls, for, every, single, one, of those, recursive, calls, we're, doing, three recursive, calls, then, we're, doing, two
1:04:37
recursive, calls, then, we're, doing, one call, simply, which, is, just, like, returning one, so, we're, not, really, doing, a, call, but we're, returning, a, value, the, number, of times, we, hit, this, base, case, is, equal, to n, factorial, which, means, we, actually, have more, than, n, factorial, recursive, calls but, the, most, we're, going, to, have, is, 2 times, n, factorial, because, any, other calls, above, this, the, sum, of, them, are going, to, be, less, than, the, amount, of, base
1:04:59
cases, that, we, have, so, we, simply, can cross, off, the, 2, here, and, we, get, n factorial, all, right that, is, going, to, wrap, up, this, video, my voice, is, officially, dying, i've, been filming, this, for, about, an, hour, and, a half, we'll, see, how, long, the, video actually, ends, up, being, but, hopefully this, was, helpful, i, understand, that, if you're, a, beginner, in, this, the, last example, is, probably, to, confuse, you, a little, bit, you, don't, have, to, stress, out
1:05:20
too, much, about, those, if, you, understood the, first, let's, say, what, do, we, go, up, to here, uh, let's, say, eight, examples, then, i think, you're, doing, really, well, with, big o, notation, i, wanted, to, throw, in, some more, advanced, ones, because, i, know, some people, are, looking, for, that, and, i, think that, will, be, helpful, to, a, few, people anyways, if, you, guys, appreciate, this video, make, sure, to leave, a, like subscribe, to, the, channel, check, out
1:05:38
programming, expert, and, i will, see, you, in another, youtube, video [Music]
1:05:50
you
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat