[Music] lesson six big O big Omega and big Theta notation when we speak of an algorithm's efficiency we want to determine its scalability that is we want to know that when the algorithm is applied to a large data set that it will finish relatively quickly we can also talk about how much memory and algorithm requires but for now we will focus on speed we measure an algorithm speed in terms of the growth in the number of operations relative to the input size for the linear and binary search algorithms for example the input size is the number of elements that we are searching typically we will use the letter N to represent an unknown input size and we will talk about the growth in terms of n to formalize our ideas of growth there are three types of bounds that we will address here big O big Omega and big Theta the definitions that we will use come from mathematics and are used to relate the growth in one function relative to another simpler one here we have the graphs of two real functions f ofx and g ofx given by the gray and dashed arrows which we Ed to indicate that the functions continue indefinitely the function f ofx is more complex and we want to measure its growth in terms of the simpler function G ofx more specific specifically we want to find a constant such that when we multiply it by the function G ofx it will bound the function f ofx above from some point onward assuming that the graph of f ofx does not intersect the graph of C * G ofx after the point x0 we know that the graph of f ofx remains in this white region for all x to the right of x0 in this case we say that f ofx is in Big O of G ofx formally we say that f ofx is in Big O of G ofx if there exist positive constants C and x0 such that f ofx is less than or equal to C * G ofx for all X greater than x0 on the other hand we could bound the function f ofx From Below like this if such a constant exists such that c * G ofx bounce F ofx below from some point onward then we say that f ofx is in big Omega of G ofx formally f ofx is in big Omega of G ofx if there exist positive constants C and x0 such that f ofx is greater than or equal to C * G ofx for all X greater than or equal to x0 if there are constants such that g ofx bounds the function f ofx both from below and above then we say that f ofx is in big Theta of G ofx X of course the constants in this case are different so we have labeled them C1 and C2 to clarify that the x0 that we choose can be any value that is far enough out that F ofx doesn't intersect either C1 * G of X or C2 * G ofx anymore and remains in this white area forly we say that f ofx is in big Theta of G ofx if there exist positive constants C1 C2 and x0 such as that C1 * G ofx is greater than or equal to F ofx which is greater than or equal to C2 * G ofx for all X greater than or equal to x0 so far we have shown what the situation looks like for General real functions for algorithms the input size is generally a positive integer like the size of an array for a sorting algorithm in this case we can think of our f and g as functions on the positive integers in mathematics X is used to signify a real variable while n is used to signify an integer variable like Hungarian notation and programming this notation allows us to see more immediately what is going on so we will use it using this notation here we see the graphs of two example functions F of N and G of n given by the solid gray and Hollow black dots respectively notice that the graphs are made up of single dots instead of Curves this is because the functions are are defined on Integer values just as we had for the real functions we can have constants such that when we multiply G of n by them we bound F of n from some point onward and the definitions are analogous here we have a constant multiple of G of n such that its graph is above the graph of f of n from some point onward the last value that puts the graph below the graph of f ofn is 2 so we can set n0 to 3 and we have F ofn in the white areas below the graph of C * G of n from 3 onward this is how we Define Big O of G of n forly we say that f ofn is in Big O of G of n if there exists a positive real number c and a positive integer n0 such that F of n is less than or equal to C * G of n for all integers n greater than or equal to n0 likewise we might have a constant multiple of a function G of n such that c * G of n bounds F of n below from some point n0 onward in this case f ofn is said to be in big Omega of G of n formally we say that f ofn is in big Omega of G of n if there exists a positive constant c and a positive integer n0 such that F of n is greater than or equal to C * G of n for all n greater than or equal to n0 additionally we can have two constant multiples of G of of n that bound the function f of n on both sides from some point n0 onward here again we say that F of n is in big Theta of G of n formally we see that F of n is in big Theta of G of n if there exist positive constants C1 and C2 and a positive integer n0 such that C1 * G of n is greater than or equal to F ofn which is greater than or equal to C2 * G of n for all n greater than or equal to n0 our purpose at this point is simply to give a visual impression of these bounds along with an exact definition in the coming lessons we will give concrete examples of how they apply to specific algorithms so that these ideas become clear this concludes the lesson