• 2 days ago
Transcript
00:00Now let's do big O notation.
00:02The time complexity has come in the form of big O notation.
00:06We write big O , we write big O , we write big O , we write big O .
00:11What does this mean? Now we will understand.
00:15The big O notation gives us our upper bound.
00:24The upper bound means that whatever program is written, whatever code is written,
00:28the time and the input size function can come out of the maximum of big O.
00:36It means that your program will run in constant time.
00:39It means that it will run in linear time.
00:41But the big O said that it will not run more than that.
00:44It means that it will not give more function value.
00:47It will not give more relation to your time and input size.
00:50Like if I have said that in some program or code or algorithm,
00:58the time complexity is big O ,
01:00so it can happen in any case.
01:02In some input size, we analyze that in big O ,
01:06the code is running in constant operations.
01:08It can happen in many cases.
01:10It can happen in big O ,
01:11it can happen in linear time.
01:12It can happen in some cases.
01:14It can happen in log N.
01:15The value of log N is small from N and N2.
01:25But I will never find N cube.
01:28Or it will never find N cube.
01:28Or it will never find N cube.
01:29Or it will never be 2 to the power N.
01:30Or it will never be 2 to the power N.
01:44Or exponential.
01:48So it will never be 2 to the power N.
01:53So it will never find N cube in common.
01:58I will never find N cube in any case.
02:00So it will never be 2 to the power N.
02:08So it will never be 3 to the power N.
02:11Like I have told you that is the worst case.
02:16also the time complexity and space complexity
02:18so that is the meaning of Big O notation
02:21in the worst case, a program can run with a time complexity
02:24Big O is to visualize it
02:26now let's take a look at how we actually solve
02:29how do we solve in Big O notation
02:30how do we solve the complexity of a program
02:33it can happen that my time
02:35and the input size
02:37is something like this
02:38it can happen that its function
02:39is ian2
02:41plus bn
02:42plus c
02:42I can say here
02:44that my a constant
02:45b constant
02:46c constant
02:47and n is my input size
02:49now if i want to convert it in Big O notation
02:52i want to tell the time complexity
02:55this is my function
02:57what is the function
02:59my fn
03:00this is my time
03:03y is equal to
03:04ax plus b
03:05y is equal to
03:06ax square plus b
03:07x plus c
03:08we can make that graph
03:10and from this graph
03:11i have removed
03:12that my time function
03:13that is equal to
03:14ax square plus b
03:16n plus c
03:17i can see
03:18my time is a function of n
03:19so if i want to convert this function
03:21into actual time complexity
03:23what will be the process of this function
03:26i have to do two things
03:27step 1
03:28to ignore constants
03:30i have to ignore all constants
03:32i have to ignore all constants
03:33i have to ignore the constants
03:34i have to ignore the constants
03:36n square plus n plus 1
03:39i have removed the fields
03:40and I have to ignore all constants
03:40and se
03:42now
03:42i have to argue step two
03:44step two is
03:44take great test
03:46take the largest term
03:50RELEASE
03:50plus minus
03:51i have to impart nationale
03:53this is just name
03:54of nth class
03:56codec equations
03:57because the term
03:58in math
04:01So most of the students, I assume from math backgrounds,
04:04I don't know, they are telling me that
04:06wherever the plus minus comes in,
04:08it becomes a term in math,
04:11in this expression.
04:12Now what is term 1 here?
04:14Term 1 is n square, term 2 is n, term 3 is 1.
04:17Which is the largest one?
04:19Obviously n square.
04:21So what will I do?
04:22I will take the largest term.
04:23So my largest term is n square,
04:26and I have put it in big O.
04:28So what is my time complexity?
04:29What is my time complexity?
04:30My time complexity is big O of n square.
04:34So what is the theoretical method?
04:36The theoretical method is that
04:37we remove the function
04:39and how it relates with time input size.
04:42After that, we ignore the constants,
04:44the largest term will be taken,
04:45and the largest term will be my time complexity.
04:48Now what happens every time?
04:49It is not practical to plot the graph.
04:51Because we have plotted a lot of graphs
04:53and it is a very difficult process.
04:56In fact, graphs are very difficult.
04:59But here, we don't plot the graph.
05:00We don't have to worry about math.
05:02We don't have to worry about math.
05:03In maximum cases,
05:05there are some common 5-6 type complexity.
05:08In maximum cases, this is the same.
05:09There are some different cases,
05:11different questions,
05:11and within them it is a little different.
05:13Therefore, there will be 5-6 time complexity.
05:15And after a little time,
05:15we will remember what was the time complexity.
05:20Now, what are our cases?
05:21In maximum cases,
05:22this is the same.
05:23And what do we do?
05:24We will do all theoretically.
05:25We will not plot the graph.
05:26We will not plot the graph.
05:26We will not plot the theory.
05:27We will plot the graph.
05:29And what is the size of the input size?
05:31We will plot the logic.
05:34We will plot the graph.
05:35We will not plot the graph.
05:36So, here, we have understood what
05:37means bigger notation.
05:39I will take another example.
05:41What do I say about this?
05:42My time,
05:44that is a function of n cube.
05:46So, I can say
05:46a n cube plus b log n plus c.
05:50I have some functions.
05:52I will do the first step of this function.
05:55So, step 1 is ignore constants.
05:57Constants are ignored.
05:58N cube plus log n plus 1.
06:01Now, I will do the next step.
06:03Largest term.
06:07When the largest term is n cube.
06:10When the largest term is n cube.
06:11So, what do we say?
06:12Time complexity will be big of n cube.
06:15So, here, the input size of the n value
06:19was also dependent on the log n.
06:22But since the largest n cube was n cube.
06:24So, my big of n cube came.
06:26If I have to visualize this in the graph.
06:28I can do this.
06:30That my time complexity is n cube.
06:32When my maximum time complexity is already out.
06:35Why do I see the log n relationship?
06:38Why do I see the log n relationship?
06:38I have to take the worst.
06:40And who will I take the worst?
06:41The worst will I take the worst?
06:42The worst will I take the n cube.
06:43This n cube could also be k n cube.
06:46I mean, k is any constant value.
06:49I will multiply the n cube.
06:50This is my time complexity.
06:52So, I use the small term of log n.
06:54Because it will be the maximum time for the big input size.
06:57The value of log n is not enough.
06:59So, I will see the n cube.
07:01I will see the n cube.
07:01I can say that my n cube graph goes this way.
07:05And my log n graph goes this way.
07:08So, if I increase the input size.
07:09I mean, my input size comes here.
07:11Where you come from.
07:11Here is where.
07:12So, if I take the time.
07:15I will take the time.
07:18I will take the time to go.
07:37and I want to see the worst time
07:39now it is possible to contribute a little bit
07:41but I have to add a little bit
07:42I always want to make the worst
07:45because it is my job
07:46so I will always see the largest term
07:47which is the maximum impact
07:50so this will be big of n cube
07:53now those students
07:55who have a little bit of math
07:58this part
07:59although we can skip the equation
08:00this is mostly college exams
08:03so if you don't study college exams
08:06so it is okay
08:07if you want to study college
08:09then it is theoretical
08:09there is no relationship with our placement
08:11there is no equation
08:15but then I will tell
08:17the students who are interested
08:18in the other algorithms
08:19there is a book called Cormin
08:21which you can read
08:23it is a very good book, it is a very classical book
08:25it is time complexity
08:26and you can read the theory
08:28and you will also get many things
08:31if you are interested in reading books
08:33if you are interested in reading books
08:34it is also time taking
08:35you have time, you have 1-2 years
08:37so you can read
08:39now time complexity
08:40in mathematical terms
08:42I always say that
08:44time is a function of n
08:47that is a function of n
08:48that is a function of n
08:50I can say that if this is my time value of fn
08:52then there will be a value here
08:54and I will analyze or derive
08:57that my time complexity
08:58will be big of some gn
09:01that is a function of n
09:04that is a function of n
09:05that is a function of n square
09:05here is an square plus bn plus c
09:08and that is n square
09:09so I can remove the relationship
09:11because this is derived from this
09:13so I can say that my fn
09:16is some big o of gn
09:19that is my time complexity
09:21that relates to big o of gn
09:23so mathematically if I have to represent big o
09:26then it means that
09:27fn by gn
09:29at limit n tends to infinity
09:32should be less than infinity
09:35this is a condition
09:36that fn is always positive
09:39so we take a mod here
09:40this is my formula
09:42that comes to represent big o
09:44in mathematical terms
09:45no one is asking you to
09:47if we don't understand the limit
09:49so we don't have to get attention
09:50we don't have to get attention
09:52if we are getting theoretically
09:52what is the meaning of big o
09:54we are getting intuitively
09:56and we will get out of programs
09:57so we don't have to get attention
09:59other people who have college exams
10:01we can remember this formula
10:03for college exams
10:04that this equation comes out
10:05when we talk about big o
10:07we can understand this equation
10:08intuitively
10:10what is n?
10:11n is my input size
10:12which I have taken an example
10:13I will tell you
10:14if I write the value of fn
10:16if I write n2
10:18plus 2n
10:19plus 3
10:20then what did I do
10:22I did it
10:22I did it
10:23that my gn is n2 always
10:25what is gn
10:26gn is big o of n2
10:28I know that
10:29the time complexity
10:30that will be big o of n2
10:32so if I apply this same thing
10:34mathematically
10:34I will apply this
10:36so I can say that
10:37n2
10:38plus 2n
10:39plus 3
10:39divided by n2
10:40here I will do
10:42limit n tends to infinity
10:43what is the value of this?
10:45individually divide
10:46n2
10:47n2
10:47n2
10:48n2
10:49n2
10:49n2
10:50n2
10:50n2
11:01n2
11:20n2
11:23n2
11:24n2
11:24n2
11:25n2
11:26n2
11:26n2
11:26n2
11:27n2
11:29n2
11:30n2
11:30n2
11:30n2
11:30n2
11:31n2
11:32So we can go into this theoretically in the government, if we know more.
11:37I'll take one summary from Big O Notation.
11:40The basic funda here is that what we have to do?
11:43We don't have to get out of worst case time complexity every time.
11:46And we will always get out of that.