Asymptotic Analysis

Introduction:

If you want to analyze two algorithms how you will measure them-

The simplest way to do it is to implement both the algorithms run them on some machine and check which one is faster. But there are so some problems associated with this approach:

  •       For some input algorithm A may perform well and for some input algorithm B may perform well.
  •    For some input algorithm A, is performing good on machine X but for the same input on machine Y algorithm B is doing good

All such problems can be handled using the asymptotic notation as in asymptotic notation the performance of the algorithm is measured in terms of input size. How the performance of algorithms grows as the input size grows. The machine-dependent constants can always be ignored after a certain value of input size.

 

Does it always work?

Asymptotic notation does not do good always for example

  • .    Two algorithms with the same growth with different machine constants cannot be compared as in asymptotic notation we ignore the constants (0.2nlogn and 1000nlogn)
  • .      In the asymptotic analysis, we analyze the algorithms for large input size, it might possible that such large inputs are never given to your algorithm which is asymptotically slower. So, you might be discarding an algorithm that fits well for your situation but is asymptotically slower.

 

The main idea of asymptotic analysis is to measure the performance of an algorithm that does not depend upon the machine-dependent constant, and doesn’t require algorithms to be implemented, and time taken by programs to be compared. 

Comments

Post a Comment

Popular posts from this blog

Worst, Average and Best Case Analysis of Algorithms

Image
Introduction:  We all understand that as the input size (n) grows, an algorithm's running time grows. Even though the input is the same size, running times can change between distinct input instances. We then conduct best, average, and worst-case analyses in that situation. In this post, we will take an example of Linear Search and will analyze its best, average, and worst-case time complexity. Consider the linear search example where we look for an item in an array. In Linear search, we simply traverse the list completely and match each element of the list with the item whose location is to be found. If the match is found, then the location of the item is returned; otherwise, the algorithm returns -1. The steps used in the implementation of Linear Search are listed as follows - First, we have to traverse the array of elements using a for a loop. In each iteration of for loop, compa...
Read more

Complexity of Loops

The time complexity of a function is O(1) if does not contain a loop, recursive function, or any other non-constant time function.  The time complexity of a loop is also O(1) if it has a constant no of iterations Recursive function time complexity is also O(1) if it runs a constant no of times. Linear Loops: The time complexity of a loop is O(n) which is linear. If the loop variable is incremented or decremented by constant Nested Loops:  1. The time complexity of nested loops is equal to the number of times the innermost statement is executed. For example, the following sample loop has  O(n 2 )  time complexity:    for (int i = 1; i <=n; i += c) {        for (int j = 1; j <=n; j += c) {           // some O(1) expressions        }    }   2. When one of the loops is divided and multiplied by constant and other loop is increm...
Read more