need throughout these video tutorials. Let's get started with the basics. So what is a

data structure? one definition that I really like is a data structure is a way of organizing

data so that it can be used efficiently. And that's all data structure really is it is

a way of organizing data in some fashion so that later on it can be accessed, queried,

or perhaps even updated quickly and easily. So why data structures? Why are they important?

Well, they are essential ingredients in creating fast and powerful algorithms. Another good

reason might be that they help us manage and organize our data in a very natural way. And

this last point, is more of my own making. And it's that it makes code cleaner and easier

to understand. As a side note, one of the major distinctions that I have noticed from

bad mediocre to excellent programmers is that the ones who really excel are the ones who

fundamentally understand how and when to use the appropriate data structure for the task

they're trying to finish. data structures can make the difference between having an

okay product and an outstanding one. It's no wonder that every computer science undergraduate

student is required to take a course in data structures. It is strange that before we even

begin talking about data structures that we need to talk about the abstraction of data

structures. What I'm talking about is the concept of an abstract data type. What is

an abstracted type and how does it differ from a data structure? Well, the answer is

that an abstract data type is an abstraction of a data structure, which provides only the

interface to which that data structure must adhere to. The interface does not give any

specific details on how

a specific data structure should be implemented, or in what programming language. One particular

example I like to give is to suppose that your abstract data type is for a mode of transportation

to get from point A to point B. Well, as we both know, there are many modes of transportation

to get from one place to another. So which one do you choose? some specific modes of

transportation might be walking or biking, perhaps even taking a train and so on, these

specific modes of transportation would be analogous to the data structures themselves.

We want to get from one place to another through some mode of transportation, that was our

abstract data type. How did we do that? Exactly? Well, that is the data structure. Here are

some examples of abstract data types on the left, and some possible underlying implementation

on the right hand side. As you can see, a list can be implemented in two ways. You can

have a dynamic array or a linked list. They both provide ways of adding, removing and

indexing elements in the list. Next, we have a queue and the map abstract data types, which

themselves can be implemented in a variety of ways. Notice that under the implementation

for a queue, I put a stack based queue because yes, you can have a queue, which is implemented

using only stacks. This may not be the most efficient way of implementing a queue. But

it does work and it is possible. The point here is that the abstract data type only defines

how a data structure should behave, and what methods it should have, but not the details

surrounding how those methods are implemented. Alright, now that we were done with abstract

data types, we need to have a quick look at the wild world of computational complexity,

to understand the performance that our data structures are providing. So as programmers,

we often find ourselves asking the same two questions over and over and over again. That

is, how much time does this algorithm need to finish and also how much space Does this

algorithm need for my computation. So, if your program takes a lifetime of the universe

to finish, then it's no good. Similarly, if your program runs in constant time, but requires

a space equal to the sum of all the bytes of all the files on the internet, internet,

your algorithm is also useless. So just standardize a way of talking about how much time and how

much space is required for an algorithm to run. theoretical computer scientists have

invented big O notation, amongst other things like big theta, big omega, and so on. But

we're interested in Big O because it tells us about the worst case. Big O notation only

cares about the worst case. So if your algorithm sorts numbers, imagine the input is the worst

possible arrangement of numbers for your particular sorting algorithm. Or, as a concrete example,

suppose you have an unordered list of unique numbers, and you're searching for the number

seven, or the position where seven occurs in your list. And the worst case isn't one

seven, that is at the beginning. Or in the middle of the list, it's one seven is the

very last element of the list. for that particular example, the time complexity would be linear

with respect to the number of elements in the size view list. Because you have to traverse

every single element until you find seven. The same concept applies to space, you can

just consider the worst possible amount of space your algorithm is going to need for

that particular input. There's also the fact that big O really only cares about what happens

when your input becomes arbitrarily large. We're not interested in what happens when

the input is small. For this reason, you'll see that we ignore things like constants and

multiplicative factors. So in our big O notation, you'll often see these coming up. Again, again,

again. So to clarify one thing,

when I say n, n is usually always want to be the input size coming into your algorithm,

there's always going to be some limitation of size n. So constant time referred to as

a one wrapped around a big O. If your algorithm case in logarithmic amount of time to finish,

we say that's big O of a log event. If it's linear, then we just say n, if it takes like

quadratic time or cubic time, then we say that's n raised to that power, it's exponential.

Usually, this is going to be something like two to the n three, the N, N number be greater

than one to the n. And then we also have n factorial. But we also have things in between

these like square root of n log log of n, n to the fifth and so on. Actually, almost

any mathematical expression containing n can be wrapped around a big O. And is big O notation

valid. Now, we want to talk about some properties of Big O. So to reiterate what we just saw

in the last two slides, Big O only really cares about what happens when input becomes

really big. So we're not interested when n is small, only

what happens when n goes to infinity. So this is how and why we get the first two properties.

The first that we can simply remove constant values added to our big O notation. Because

if you're adding a constant to infinity, well, let's just infinity, or if you're multiplying

a constant by infinity, yeah, that's still infinity. So we can ignore constants. But

of course, this is all theoretical. In the real world. If your constant is of size, 2

billion, probably, that's going to have a substantial impact on the running time of

your algorithm.

However, let us look at a function f, which I've defined over some input size. And if

f of n is seven log of n cubed plus 15 n squared plus two n q plus eight. Well, big O of f

of n is just n cubed, because n cubed is the biggest, most dominant term in This function.

All right, now let's

look at some concrete examples of how big O is used. So both of the following run in

constant time with respect to the input size, and because they don't depend on n

at all.

So on the left, when we're just adding or doing some mathematical formula, yes, that's

constant time. And on the right, okay, we're doing a loop, but the loop itself doesn't

depend on n. So it runs also in a constant amount of time. So as our input size gets

arbitrarily large, well, that loop is still going to run in the same amount of time regardless.

Now let's look at a linear example. So both the following actually run in

linear time with respect to the input size, and because we do a constant amount of work,

and times.

So on the left, we're incrementing, the counter AI by one each time. So f of n is and, and

clearly, when we wrap this in a big go get a big O of n. On the right, a little bit more

complicated, we're not incrementing by one, we're incrementing by three, so we're going

to finish that loop three times faster. So f of n is n over three. So our second example

is two algorithms that run in quadratic time. So the first one seems obvious, we do n work

at times. So n times as big O of n squared. But observe the second one, I changed the

zero with an eye. So pause the video and try to figure out maybe why that's big O of n

squared. Okay, let's go over the solution. So first, just focus on the second loop. The

first loop isn't as important. So since I go from zero to n, the amount of looping done

is going to be directly related to what AI is, and remember is changing from the outer

loop. So if we fix AI to be zero, we do n work. We fix it one, we do n minus one work.

If we fix it, too, we do n minus two work and excetera. So the question then becomes

what is n plus n minus one plus n minus two plus n minus three and so on? Well, this is

a well known identity, and turns out to be n times n plus one divided by two. So if we

wrap this in a big O, we split our equation, we can see that this is big O of n squared.

Now let's look at perhaps a more complicated example. Earlier, you may have wondering,

how do we ever get these log Eurythmics or linear rhythmic time complexities? So here's

a classic algorithm of doing a binary search, which yields actually a logarithmic time complexity.

So what this algorithm does is it starts by making two pointers, one at the very start

in one at the very end of the array, then it selects a midpoint between two and checks

if the value we're looking for was found at the midpoint, and then has either found it

or not, if it has found it, it stops. Otherwise, it discards one half of the array, and adjusts

either the high or the low pointer. remark that even in the worst case, we're still discarding

half of the array, each iteration. So very, very quickly, we're going to run out of a

range check. So if you do the math, the worst case is you will do exactly log base two of

N iterations, meaning that the binary search will runs in logarithmic time. Very cool algorithm,

a very powerful algorithm. Here's a slightly different example worth going over. So first,

notice that there is an outer loop with a counter I that does and work, then notice

that there are two inner loops, one that does three n work another one that does, too, one

work. So the rule we use to determine the complexity of this algorithm is to multiply

loops on different levels and add those that aren't the same, generally speaking. So, so

using the rule above, we can see that it takes n work to do the outer loop, multiply by three

n plus two n for both inner loop Which gives us five n squared, which is big O of n squared.

All right, so this next one looks very similar, but it's actually quite different. So on the

outer loop with AI, we have AI going from zero to three n. So there's three n work done

on the outside. But we have to multiply that but what's going on on the inside,

so the inside

j goes from 10, to 50. So that does 40 loops exactly every loop. So that's a constant for

the amount of work. Plus however, the second loop, so j is less than and cubed, but j is

J equals j plus two, so it's accelerated a little, so we're going to finish that loop

a little faster. So we're gonna get on the inside 14, plus n cubed divided by two, but

we have to multiply that by three n. So we wrap that in a big O. So big O of f of n,

is going to give us big of enter the force, because And the fourth is the dominant term

in our function, f of n. For some other classic examples of Big O. So if we have to find all

the subsets of a set, that takes an exponential amount of time, because there are two the

N subsets, finding all permutations of a string takes big O of n factorial. Another classic

one is merge sort. So we have n times log in for your merge sort. And if we have to

iterate over all the cells of an array of size n by n, we have big O of n m. Time. All

right, let's talk about arrays, probably the most used data structure. This is part one

of two in the array videos. The reason the array is used so much is because it forms

a fundamental building block for all other data structures. So we end up seeing everywhere.

with arrays and pointers alone, I'm pretty sure we can construct just about any data

structure. So an outline for today's video. First, we're going to begin by having a discussion

about arrays and answer some fundamental questions such as what where and how are arrays used?

Next, I will explain the basic structure of an array and the common operations we are

able to perform on them. Lastly, we will go over some complexity complexity analysis and

look at some source code on how to construct a dynamic array using only static arrays,

discussion and examples. So what is a static array? So static array is a fixed length container

containing elements, which are indexable, usually on the range of zero, inclusive to

n minus one also inclusive. So a follow up question is what is meant by being indexable?

So answer this is this means that each slot or index in the array can be referenced with

a number. Furthermore, I would like to add that static arrays are given as contiguous

chunks of memory. Meaning that your chunk of memory doesn't look like a piece of Swiss

cheese with a bunch of holes and gaps. It's continuous, all the addresses are adjacent

in your static array. Okay, so when and where is a static array used? Well, they're used

everywhere, absolutely everywhere. It's hard to make a program that doesn't use them. In

fact, here are a few places you may or may not know that do use arrays. So of course,

the first simple example is to temporarily store objects most common use of arrays that

you're probably familiar with. Next is that we use arrays as buffers to store information

from an input or an output stream. Suppose you have a really large file, for instance,