DS4Fun

When we use the big-θ notation bounds, a function from above and below; so it defines the exact asymptotic tight bound. Average case analysis. Tight bound of an algorithm. O(g(n)) - {f(n): there exist constants c1, c2 & n 0 such that 0<=c1.g(n) <= f(n) <= c2.g(n) for n>=n 0 }. Once n gets large enough, the running between c1.g(n) and c2.g(n). Let's understand it with the help of the program. private boolean searchValue( int [] n, int targetValue) { for ( int i = 0 ; i < n. length ; i++) { if (n[i] == targetValue) return true ; } return false ; } As per the above program, It will never go beyond the limit of θ(n) runtime analysis in the large value of n. There are two basic rule for Big-Theta (θ):- Drop lower order terms. Drop constants. If T(n) = 2n 2 + 2 then it will be 0 <= 2n 2 <= 2n 2 + 2 <= 3n 2   and it mean θ(n 2 ).

Big-O notation Worst-case analysis. Upper bound of an algorithm. O(g(n)) - {f(n) : there exist constants c and n 0  such that 0<=f(n)<=cg(n) for all n >= n 0 } It is commonly used to calculate time analysis of an algorithm, it will give us an upper bound limit which doesn't exceed any input size. You can clearly see in the below diagram after a particular size of the input (n 0  ) after then the f(n) always lies in or below the c.g(n). There are two basic rules for Big-Oh (0) Drop lower order term Drop constants Let's understand the above rules in an example:- int a = 1 ; // O(1) int b = 2 ; // O(1) int c = 3 ; // O(1) for ( int i = 1 ; i <= n; i++) { // O(n + 1) for ( int i1 = 1 ; i1 <= n; i1++) { // O(n +1) a = i*i1; // O(1) b = i*i1; // O(1) c = i*i1; // O(1) } } for ( int i = 0 ; i < n; i++) { // O(n) a *= i; // O(1) b *= i; // O...

Whenever we solve any problem there is a sequence of steps that needs to be followed. We have already read the term algorithm, which is nothing but a sequence of steps to achieve the result. Our algorithm took some time and space to solve it. The running time depends upon several factors:- Single/Multiple processor system. R/W speed to memory. CPU speed. 32/64 bit system. Input Size. Do we really need all the factors to calculate the time complexity? Don't you think the hardware couldn't be a factor in the time calculation of the algorithm? Let's understand this in more detail. For example, Kavya and I are working on the problem that needs us to calculate the sum of n natural numbers. We come up with a different-2 approach to solve the problem. Now, Kavya has an i7 machine and running the code, it takes less than 1 ms and I have a dual-core machine that takes 5ms and there is a huge possibility that when I run the same code in a high configuration machine then i...