Learn Big-O Notation in 100 Seconds (of Computer Science). ⚡🔬

#compsci #100SecondsOfCode

Install the quiz app 🤓

iOS https://itunes.apple.com/us/app/fireship/id1462592372?mt=8
Android https://play.google.com/store/apps/details?id=io.fireship.quizapp

Upgrade to Fireship PRO at https://fireship.io/pro
Use code lORhwXd2 for 25% off your first payment. 

My VS Code Theme

- Atom One Dark 
- vscode-icons
- Fira Code Font
2024-02-04T06:26:05.443Z
nova-2
2-general-nova
2024-01-09.29447
30089e05-99d1-4376-b32e-c263170674af
c0fa8e82-b74c-485d-b4c8-9e7cbc35c076
74dcefeb2a945bc4831cf5933b8f6db6decfd526122d31114df5dc65dc5e8747
67875a7f-c9c4-48a0-aa55-5bdb8a91c34a
deprecated
Big O notation, a way to describe how well an algorithm performs as its input size grows.
As we add more inputs or data points to an algorithm, there are 2 things that might grow in complexity.
It may take longer to run the algorithm, which we call time complexity, or it may require more memory, which we call space complexity.
It.
The variable n represents the number of inputs.
Now imagine n being scaled up to infinity.
The faster the result grows after each step, the worse your algorithm performs.
It.
In technical interviews, you'll often be asked to estimate the time or space complexity of the code you've implemented.
Take for example a loop over an array of elements.
It.
It takes exactly one unit of time to loop over each element.
This is known as linear complexity because we have a perfect one to one relationship between the number of inputs and the amount of time it takes to execute the algorithm.
But we can often do better than linear time.
If we have a sorted array, we can implement a binary search where we start the middle and then jump back and forth until we find the actual value we're looking for.
This is known as logarithmic complexity and it scales much better to a large number it inputs.
At the most efficient end of the spectrum we have constant time.
An example is looking up an element in an array by its index.
It.
No matter how big that array is, it should always take the same amount of time.
But things can also get less efficient.
Imagine a loop within a loop.
It.
This is quadratic complexity where the number of inputs is raised to the power of 2, and things can still get worse with exponential complexity.
Imagine looping over every possible combination in an array.
Some algorithms may have multiple different growth rates of complexity.
Always simplify your notation down to the fastest growing worst case scenario.
It.
This has been Big O Notation in 100 seconds.
Thanks for watching, and I will see you in the next one.

Speaker 0: Big O notation, a way to describe how well an algorithm performs as its input size grows. As we add more inputs or data points to an algorithm, there are 2 things that might grow in complexity. It may take longer to run the algorithm, which we call time complexity, or it may require more memory, which we call space complexity. It. The variable n represents the number of inputs.

Now imagine n being scaled up to infinity. The faster the result grows after each step, the worse your algorithm performs. It. In technical interviews, you'll often be asked to estimate the time or space complexity of the code you've implemented. Take for example a loop over an array of elements.

It. It takes exactly one unit of time to loop over each element. This is known as linear complexity because we have a perfect one to one relationship between the number of inputs and the amount of time it takes to execute the algorithm. But we can often do better than linear time. If we have a sorted array, we can implement a binary search where we start the middle and then jump back and forth until we find the actual value we're looking for.

This is known as logarithmic complexity and it scales much better to a large number it inputs. At the most efficient end of the spectrum we have constant time. An example is looking up an element in an array by its index. It. No matter how big that array is, it should always take the same amount of time.

But things can also get less efficient. Imagine a loop within a loop. It. This is quadratic complexity where the number of inputs is raised to the power of 2, and things can still get worse with exponential complexity. Imagine looping over every possible combination in an array.

Some algorithms may have multiple different growth rates of complexity. Always simplify your notation down to the fastest growing worst case scenario. It. This has been Big O Notation in 100 seconds. Thanks for watching, and I will see you in the next one.
Big O notation, a way to describe how well an algorithm performs as its input size grows. As we add more inputs or data points to an algorithm, there are 2 things that might grow in complexity. It may take longer to run the algorithm, which we call time complexity, or it may require more memory, which we call space complexity. It.
The variable n represents the number of inputs. Now imagine n being scaled up to infinity. The faster the result grows after each step, the worse your algorithm performs. It. In technical interviews, you'll often be asked to estimate the time or space complexity of the code you've implemented. Take for example a loop over an array of elements. It. It takes exactly one unit of time to loop over each element. This is known as linear complexity because we have a perfect one to one relationship between the number of inputs and the amount of time it takes to execute the algorithm.
mathematics
machine learning
programming
But we can often do better than linear time. If we have a sorted array, we can implement a binary search where we start the middle and then jump back and forth until we find the actual value we're looking for. This is known as logarithmic complexity and it scales much better to a large number it inputs. At the most efficient end of the spectrum we have constant time. An example is looking up an element in an array by its index. It. No matter how big that array is, it should always take the same amount of time. But things can also get less efficient. Imagine a loop within a loop. It. This is quadratic complexity where the number of inputs is raised to the power of 2, and things can still get worse with exponential complexity.
Imagine looping over every possible combination in an array. Some algorithms may have multiple different growth rates of complexity. Always simplify your notation down to the fastest growing worst case scenario. It. This has been Big O Notation in 100 seconds. Thanks for watching, and I will see you in the next one.
mathematics
machine learning
measurement
Big O notation, a way to describe how well an algorithm performs as its input size grows. As we add more inputs or data points to an algorithm, there are 2 things that might grow in complexity. It may take longer to run the algorithm, which we call time complexity, or it may require more memory, which we call space complexity. It. The variable n represents the number of inputs. Now imagine n being scaled up to infinity. The faster the result grows after each step, the worse your algorithm performs. It. In technical interviews, you'll often be asked to estimate the time or space complexity of the code you've implemented. Take for example a loop over an array of elements. It. It takes exactly one unit of time to loop over each element. This is known as linear complexity because we have a perfect one to one relationship between the number of inputs and the amount of time it takes to execute the algorithm. But we can often do better than linear time. If we have a sorted array, we can implement a binary search where we start the middle and then jump back and forth until we find the actual value we're looking for. This is known as logarithmic complexity and it scales much better to a large number it inputs. At the most efficient end of the spectrum we have constant time. An example is looking up an element in an array by its index. It. No matter how big that array is, it should always take the same amount of time. But things can also get less efficient. Imagine a loop within a loop. It. This is quadratic complexity where the number of inputs is raised to the power of 2, and things can still get worse with exponential complexity. Imagine looping over every possible combination in an array. Some algorithms may have multiple different growth rates of complexity. Always simplify your notation down to the fastest growing worst case scenario. It. This has been Big O Notation in 100 seconds. Thanks for watching, and I will see you in the next one.
Big
big
O
o
notation,
notation
a
a
way
way
to
to
describe
describe
how
how
well
well
an
an
algorithm
algorithm
performs
performs
as
as
its
its
input
input
size
size
grows.
grows
As
as
we
we
add
add
more
more
inputs
inputs
or
or
data
data
points
points
to
to
an
an
algorithm,
algorithm
there
there
are
are
2
2
things
things
that
that
might
might
grow
grow
in
in
complexity.
complexity
It
it
may
may
take
take
longer
longer
to
to
run
run
the
the
algorithm,
algorithm
which
which
we
we
call
call
time
time
complexity,
complexity
or
or
it
it
may
may
require
require
more
more
memory,
memory
which
which
we
we
call
call
space
space
complexity.
complexity
It.
it
The
the
variable
variable
n
n
represents
represents
the
the
number
number
of
of
inputs.
inputs
Now
now
imagine
imagine
n
n
being
being
scaled
scaled
up
up
to
to
infinity.
infinity
The
the
faster
faster
the
the
result
result
grows
grows
after
after
each
each
step,
step
the
the
worse
worse
your
your
algorithm
algorithm
performs.
performs
It.
it
In
in
technical
technical
interviews,
interviews
you'll
you'll
often
often
be
be
asked
asked
to
to
estimate
estimate
the
the
time
time
or
or
space
space
complexity
complexity
of
of
the
the
code
code
you've
you've
implemented.
implemented
Take
take
for
for
example
example
a
a
loop
loop
over
over
an
an
array
array
of
of
elements.
elements
It.
it
It
it
takes
takes
exactly
exactly
one
one
unit
unit
of
of
time
time
to
to
loop
loop
over
over
each
each
element.
element
This
this
is
is
known
known
as
as
linear
linear
complexity
complexity
because
because
we
we
have
have
a
a
perfect
perfect
one
one
to
to
one
one
relationship
relationship
between
between
the
the
number
number
of
of
inputs
inputs
and
and
the
the
amount
amount
of
of
time
time
it
it
takes
takes
to
to
execute
execute
the
the
algorithm.
algorithm
But
but
we
we
can
can
often
often
do
do
better
better
than
than
linear
linear
time.
time
If
if
we
we
have
have
a
a
sorted
sorted
array,
array
we
we
can
can
implement
implement
a
a
binary
binary
search
search
where
where
we
we
start
start
the
the
middle
middle
and
and
then
then
jump
jump
back
back
and
and
forth
forth
until
until
we
we
find
find
the
the
actual
actual
value
value
we're
we're
looking
looking
for.
for
This
this
is
is
known
known
as
as
logarithmic
logarithmic
complexity
complexity
and
and
it
it
scales
scales
much
much
better
better
to
to
a
a
large
large
number
number
it
it
inputs.
inputs
At
at
the
the
most
most
efficient
efficient
end
end
of
of
the
the
spectrum
spectrum
we
we
have
have
constant
constant
time.
time
An
an
example
example
is
is
looking
looking
up
up
an
an
element
element
in
in
an
an
array
array
by
by
its
its
index.
index
It.
it
No
no
matter
matter
how
how
big
big
that
that
array
array
is,
is
it
it
should
should
always
always
take
take
the
the
same
same
amount
amount
of
of
time.
time
But
but
things
things
can
can
also
also
get
get
less
less
efficient.
efficient
Imagine
imagine
a
a
loop
loop
within
within
a
a
loop.
loop
It.
it
This
this
is
is
quadratic
quadratic
complexity
complexity
where
where
the
the
number
number
of
of
inputs
inputs
is
is
raised
raised
to
to
the
the
power
power
of
of
2,
2
and
and
things
things
can
can
still
still
get
get
worse
worse
with
with
exponential
exponential
complexity.
complexity
Imagine
imagine
looping
looping
over
over
every
every
possible
possible
combination
combination
in
in
an
an
array.
array
Some
some
algorithms
algorithms
may
may
have
have
multiple
multiple
different
different
growth
growth
rates
rates
of
of
complexity.
complexity
Always
always
simplify
simplify
your
your
notation
notation
down
down
to
to
the
the
fastest
fastest
growing
growing
worst
worst
case
case
scenario.
scenario
It.
it
This
this
has
has
been
been
Big
big
O
o
Notation
notation
in
in
100
100
seconds.
seconds
Thanks
thanks
for
for
watching,
watching
and
and
I
i
will
will
see
see
you
you
in
in
the
the
next
next
one.
one
success
The speaker explains the complexities of algorithms, including time and space complexity, and how they can be improved with Big O notation. They use an example of a loop over an array to illustrate the scale of the problem and how efficient it can be. The speaker also mentions that algorithms can get worse with exponential complexity and that there is a way to simplify notation if the number of inputs is large.
Big-O Notation in 100 Seconds
Big O notation, a way to describe how well an algorithm performs as its input size grows. As we add more inputs or data points to an algorithm, there are 2 things that might grow in complexity. It may take longer to run the algorithm, which we call time complexity, or it may require more memory, which we call space complexity. It. The variable n represents the number of inputs. Now imagine n being scaled up to infinity. The faster the result grows after each step, the worse your algorithm performs. It. In technical interviews, you'll often be asked to estimate the time or space complexity of the code you've implemented. Take for example a loop over an array of elements. It. It takes exactly one unit of time to loop over each element. This is known as linear complexity because we have a perfect one to one relationship between the number of inputs and the amount of time it takes to execute the algorithm. But we can often do better than linear time. If we have a sorted array, we can implement a binary search where we start the middle and then jump back and forth until we find the actual value we're looking for. This is known as logarithmic complexity and it scales much better to a large number it inputs. At the most efficient end of the spectrum we have constant time. An example is looking up an element in an array by its index. It. No matter how big that array is, it should always take the same amount of time. But things can also get less efficient. Imagine a loop within a loop. It. This is quadratic complexity where the number of inputs is raised to the power of 2, and things can still get worse with exponential complexity. Imagine looping over every possible combination in an array. Some algorithms may have multiple different growth rates of complexity. Always simplify your notation down to the fastest growing worst case scenario. It. This has been Big O Notation in 100 seconds. Thanks for watching, and I will see you in the next one.
The speaker explains the complexities of algorithms, including time and space complexity, and how they can be improved with Big O notation. They use an example of a loop over an array to illustrate the scale of the problem and how efficient it can be. The speaker also mentions that algorithms can get worse with exponential complexity and that there is a way to simplify notation if the number of inputs is large.