JavaTBrains

Having the expression for the best, average and worst cases, for all the three cases we need to identify the upper and lower bounds. To represent these upper and lower bounds we need some kind of syntax and that is the subject of the following discussion about different notations. Let us assume that the given algorithm is represented in the form of function f(n). Big-O Notation: Big-O Notation gives the tight upper bound of the given function. Generally, it is represented as f(n)=O(g(n)). That means, at larger values of n, the upper bound of f(n) is g(n). For example, f(n) = n 4  + 100n 2  + 10n + 50 is the given algorithm, then n 4  is g(n). That means g(n) gives the maximum rate of growth for f(n) at larger values of n. Let us see the O-notation with little more details. O- notation defined as O(g(n))={f(n): there exists positive constants c and n 0 }. g(n) is an asymptotic tight upper bound for f(n). Our objective is to give smallest rate of growth g(n) which is gre

To analyse the given algorithm we need to know on which inputs the algorithm will takes less time and long time. We have already seen that an algorithm can be represented in the form of an expression.  That means we represent the algorithm with multiple expressions: one of the case where it takes less time and other for the case where it takes the more time. In general the first case is called the ‘Best Case’ and second case is called the ‘Worst Case’ of the algorithm. To analyse an algorithm we need some kind of syntax and that forms the base for asymptotic analysis/notation. There are three types of analysis: Worst Case: Defines the input for which the algorithm takes long time. Input is the one for which the algorithm runs the slower. Best Case: Defines the input for which the algorithm takes lowest time. Input is the one for which the algorithm runs the fastest. Average Case: Provides a prediction about the running time of the algorithm. Assumes that the

The rate at which the running time increases as a function of input is called  rate of growth . Let us assume that you went a shop to buy a car and a cycle. If your friend sees you there and  asks what you’re buying then in general you say buying a car. This is because, cost of car is too big compared to cost of cycle (approximating cost of cycle to cost of car). TotalCost = cost_of_car + cost_of cycle TotalCost ≈ cost_of_car ( approximation ) For the above mentioned example, we can represent the cost of car and cost of cycle in terms of function and for a given function ignore the low order terms that are  relatively insignificant (for large value of input size, n). As an example in the case below, n 4 , 2n 2 ,100n and 500 are the individual costs of some function and approximate it to n 4 . Since, n 4  is the highest rate of growth.                               n 4 + 2n 2 + 100n + 500 ≈ n 4 Commonly used Rate of Growth: Given below is the list of rate of growths

Data Structure: Data Structure is a particular way of storing and organizing data in a computer. So, that it can be used efficiently. We can also say in the way of data structure is a special format for organizing and storing data. General data structure types include arrays, files, linked list, stacks, queues, trees, graphs and so on. Depending on the organization of the elements, data structures are classified into two types. Linear Data Structures:  Elements are accessed in a sequential order. But, it not compulsory to store all elements in sequentially. Ex: Linked List, stacks and Queues. Non-Linear Data Structures:  Elements of this data structures are sorted/accessed in a non-linear order. Ex: Trees and Graphs. Algorithms: The formal definition of an algorithm is the step-by-step instructions to solve a given problem. Let us consider the problem of preparing an omelet. For preparing omelet, general steps we follow are: Get the frying pan Get the oil a. Do we hav