time complexity

 Time Complexity


Time Complexity of algorithm/code is not equal to the actual time required to execute a particular code but the number of times a statement executes.You will get surprising results i.e. for N = 10 you may get 0.5ms time and for N = 10, 000 you may get 0.2 ms time. Also, you will get different timings on the different machine. So, we can say that actual time requires to execute code is machine dependent (whether you are using pentium1 or pentiun5) and also it considers network load if your machine is in LAN/WAN. Even you will not get the same timings on the same machine for the same code, the reason behind that the current network load. 

Now, the question arises if time complexity is not the actual time require executing the code then what is it? 

The answer is : Instead of measuring actual time required in executing each statement in the code, we consider how many times each statement execute. 

How to Compare Algorithms?

To compare algorithms, let us define a few objective measures:

  • Execution times: Not a good measure as execution times are specific to a particular computer.
  • A number of statements executed: Not a good measure, since the number of statements varies with the programming language as well as the style of the individual programmer.
  • Ideal solution:  Let us assume that we express the running time of a given algorithm as a function of the input size n (i.e., f(n)) and compare these different functions corresponding to running times. This kind of comparison is independent of machine time, programming style, etc.

Worst Case Analysis (Usually Done) 
In the worst case analysis, we calculate upper bound on running time of an algorithm. We must know the case that causes maximum number of operations to be executed. For Linear Search, the worst case happens when the element to be searched (x in the above code) is not present in the array. When x is not present, the search() functions compares it with all the elements of arr[] one by one. Therefore, the worst case time complexity of linear search would be Θ(n).

Average Case Analysis (Sometimes done) 
In average case analysis, we take all possible inputs and calculate computing time for all of the inputs. Sum all the calculated values and divide the sum by total number of inputs. We must know (or predict) distribution of cases. For the linear search problem, let us assume that all cases are uniformly distributed (including the case of x not being present in array). So we sum all the cases and divide the sum by (n+1). Following is the value of average case time complexity. 
 In the best case analysis, we calculate lower bound on running time of an algorithm. We must know the case that causes minimum number of operations to be executed. In the linear search problem, the best case occurs when x is present at the first location. The number of operations in the best case is constant (not dependent on n). So time complexity in the best case would be Θ(1) 

Most of the times, we do worst case analysis to analyze algorithms. In the worst analysis, we guarantee an upper bound on the running time of an algorithm which is good information. 
The average case analysis is not easy to do in most of the practical cases and it is rarely done. In the average case analysis, we must know (or predict) the mathematical distribution of all possible inputs. 

Comments

Post a Comment

Popular posts from this blog

#2 Library Management Software

 Library Management Software using Python This is the basic python classes and objects project which is used to manage library data . In this software you can declare a library and books present in it and it offers you following options You can see all the books available for rent. You can update the library with new books,remove the books This software can tell you which student has issued which books from library This will inform you if the book you want to let is not in library.  If you want to know which person has taken a particular book then you have simply to enter the name of book and this programme will simply tell you name of person. Code for the programme ********************************************* class library : def __init__ ( self ,list_of_books,library_name): self .list_of_books = list_of_books self .name_of_library = library_name self .book_lender = {} def display_book ( self ): """Function for displaying books...
Read more

#3 Water remainder Programme

 Water remainder Programme  In this software, you simply have to enter the timing after you want to drink water and it will remind you  by playing music and you have to enter stop to stop the music . in those time interval and also note the timings in the text file that in which time and which day you eat water how many times, and is it is useful to you or not. If you want to download whole the file and data as well here is the link. Simply download the whole data files given below and after downloading copy the whole files in a separate folder and open your code editor software in this folder and enjoy the programme.  Download Text file Download Sound(wav) file Download Python file Code For this program, Whole this code is written in Python file above. Note = Please add a timing.txt file and a  ".wav" 'file in your directory while running this program *************************** #importing some modules from pygame import mixer import time import datetime from w...
Read more