Comparison of algorithms

Replies

• 

  Ankit Litoriya

  Talk is cheap , show me the code.
  
  EDIT : To understand better.
  
  As much i guess time complexity for both of your algorithms is O(1) as per you are saying and code completion is depend upon the system execution cycle but in your second algorithm you are going one step further by first storing result in a variable and then printing it so why don't we compare algo's according to their steps.
  
  Is that the question you are asking ?
  Ans we compared algorithms on different bases like ...
  
  Time complexity The way in which the number of steps required by an algorithm varies with the size of the problem it is solving. Time complexity is normally expressed as an order of magnitude, e.g. O(N^2) means that if the size of the problem (N) doubles then the algorithm will take four times as many steps to complete.
  
  Space complexity The way in which the amount of storage space required by an algorithm varies with the size of the problem it is solving. Space complexity is normally expressed as an order of magnitude, e.g. O(N^2) means that if the size of the problem (N) doubles then four times as much working storage will be needed.
  
  Sometimes we get confuse in between Auxiliary space and Space complexity. Here's the correct definitions of them Auxiliary Space is the extra space or temporary space used by an algorithm. Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.
  
  For example, if we want to compare standard sorting algorithms on the basis of space, then Auxiliary Space would be a better criteria than Space Complexity. Merge Sort uses O(n) auxiliary space, Insertion sort and Heap Sort use O(1) auxiliary space. Space complexity of all these sorting algorithms is O(n) though.
  
  Source : GeeksforGeeks | A computer science portal for geeks
  
• 

  radha gogia

  Ankit Litoriya

  Talk is cheap , show me the code.
  
  EDIT : To understand better.
  
  As much i guess time complexity for both of your algorithms is O(1) as per you are saying and code completion is depend upon the system execution cycle but in your second algorithm you are going one step further by first storing result in a variable and then printing it so why don't we compare algo's according to their steps.
  
  Is that the question you are asking ?
  Ans we compared algorithms on different bases like ...
  
  Time complexity The way in which the number of steps required by an algorithm varies with the size of the problem it is solving. Time complexity is normally expressed as an order of magnitude, e.g. O(N^2) means that if the size of the problem (N) doubles then the algorithm will take four times as many steps to complete.
  
  
  
  Space complexity The way in which the amount of storage space required by an algorithm varies with the size of the problem it is solving. Space complexity is normally expressed as an order of magnitude, e.g. O(N^2) means that if the size of the problem (N) doubles then four times as much working storage will be needed.
  
  Sometimes we get confuse in between Auxiliary space and Space complexity. Here's the correct definitions of them Auxiliary Space is the extra space or temporary space used by an algorithm. Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.
  
  For example, if we want to compare standard sorting algorithms on the basis of space, then Auxiliary Space would be a better criteria than Space Complexity. Merge Sort uses O(n) auxiliary space, Insertion sort and Heap Sort use O(1) auxiliary space. Space complexity of all these sorting algorithms is O(n) though.
  
  Source : GeeksforGeeks | A computer science portal for geeks

  Yes I really want to know why aren't we comparing algorithms on the basis of statements ,because as you said that auxiliary space is the extra space used by an algorithm ,so doesn't that mean that if an algorithm has more number of statements ,then when it will be actually implemented on the system,it would take more time for execution .
• 

  Ankit Litoriya

  radha gogia

  Yes I really want to know why aren't we comparing algorithms on the basis of statements ,because as you said that auxiliary space is the extra space used by an algorithm ,so doesn't that mean that if an algorithm has more number of statements ,then when it will be actually implemented on the system,it would take more time for execution .

  Yeah ! Time taken for execution of code depends upon the system execution cycle for second one.
  But as it is varies according to system mechanism so we need to take care for this and that is why in general we take worst case scenario time complexity for an algorithm (As this is the worst time an algorithm take to complete without caring how cycles of execution OS does ) thats it.
  
  If you wants to know more i suggest you to go through operating system concepts of Galvin.
  and see again which part goes inn heap memory which goes in data segment you will really clearly understand.
  
  As it is not possible to describe all concepts here, so i recommend to please go there and understand the concepts OS too.
  
  I can only guide that much, hope it helps you.
• 

  rahul69

  radha gogia

  Yes I really want to know why aren't we comparing algorithms on the basis of statements ,because as you said that auxiliary space is the extra space used by an algorithm ,so doesn't that mean that if an algorithm has more number of statements ,then when it will be actually implemented on the system,it would take more time for execution .

  Well if you want to know why, here is an example,
  see both code snippets, and tell which is faster:
  

  int i=1;
  i=i+1;
  i=i+1;
  i=i+2;
  i=i+1;
  i=i+1;
  i=i+1;
  
  cout<
  for(int i=0;i<1000;i++)
  cout<If you said first is faster, then you are right. It has more statements (as we can see more there), but second code has more statements for the compiler (some 1000+ statements).
  
  radha gogia
  say for adding two numbers in one algorithm ,I simply display the addition of two numbers and in other algorithm ,I first store the result in another variable and then display that variable ,so in general which algorithm would execute fast,can we raise up this question or not because I guess on the real machine both algorithms will take different time for execution,so why are algorithms not compared on the basis of number of statements
  but in first algo u mentioned, system will display, but while calculating, it will store the value (in its default register) as storage will happen, whether we provide or not, hence first algo will also take time. 
  
  Hope it helps.
                                      

• 

  simplycoder

  I would start by saying, time is what really matters.
  Basic question is how much maximum operation on data can be handled in minimum possible time.
  Our research domains are focused on higher input size, rather than the code which is used to arrive at a solution.
  
  Coding is just a tool used to perform ardent tasks which would take way too longer if the computations were done by hand.
  
  I would say, size of program won't really matter in terms of asymptotic bounds.
  and it can be treated as a negligible.
  Let say an algorithm A, takes O(n) time when compared to input size and an algorithm B, takes O(pow(n,2)).
  
  Now even if A has more lines of code than in B, then too this would not matter when the input size is large(asymptotic).
  
  Algorithm B would be much much slower than algorithm A when it comes to the time that is taken to solve a problem(time is what matters).
  example:
  bubble sort is simple algorithm short and sweet as well.
  try writing a comparatively complex sorting algorithm like radix sort or counting sort
  later would outperform bubble sort with huge margin as the size would go higher, irrespective of the line of codes taken by both.