How to Compare Two Algorithms

Let’s understand this with a story. Alice,Bob, and john are best friends, Let’s assume Alice and Bob took a programming course this semester and john didn’t. john went to hangout with alice and bob. conversation goes like this.

John: “Hey Alice what are you doing ?”
Alice: “We are writing programs for our assignments."
John: “Hey Bob are You coding the same problem ?"
Bob:“Yes."
John: “It’s look like alice code is more efficient than your’s isn’t it?"
Bob:“Why do you think so ?"
John:“As length of her program is lesser."
Bob: “we can’t compare two Algorithm by just number of lines of code ."
John: “why?"
Bob: “Suppose if i have written a program in c in 100 lines then i can write same program in python in 20 lines or less that doesn’t mean c program is less efficient than python”
John: “Then you must be comparing it with running time. right ? “
Bob: " Nope .we can not compare two Algorithm by execution time."
John: “why ?"
Bob: “Because suppose Alice computer is faster than mine . My computer will take more time to run than her."
John: “What if we run both program on same computer ?"
Bob: “Well, there are a lot’s of processes running at same time. suppose i am playing a game and running this program same time then game is hogging all my memories that might slow my program. even if i would run same program on my computer multiple times, execution time would be different each time and the differnce between these execution time would be random. to compare them by execution time you must have to determine CPU time."
John:“Then Why don’t you calculate CPU time ?"
Bob:“Measuring CPU time is difficult. If you are running on a multi-user machine, then elapsed time is not the correct measure. You must measure CPU time. But for certain programming languages, additional features might run at unpredictable results and you may not wish to include these in your measurements. For example, if you use Java, the Java garbage collector will run at various points to reclaim the memory space used by unneeded objects. You may want to exclude from your measurements any time spent garbage collecting. Another problem is that the timing commands provided by many programming languages do not report times to a sufficient level of precision. for most problems there can be many bottleneck test cases you have to find out CPU time of program for each test case and then take average of that to find out execution time."
John: “Then what is best way to compare two Algorithms ?"
Bob: “There is a notation called asymptotic notation to measure efficiency of Algorithm."
John: “It sounds like complex. can you explain it in simple way ?"
Bob: " it’s not complex . in asymptotic notation we always talk about rate of growth of program.rate of growth means how does the execution time changes as the size of input grows. for example if you have to print a number from 1 to n then it will take linear time why ? because run time of your program is proportional to n . how do you know that ? suppose if n is 10 then your print statement will execute 10 times if i change n to 100 then print statement will execute 100 times. as n is grows 10 times your task of printing is also grows 10 times."

	#include<stdio.h>
	int main(){
	int n;
	scanf("%d",&n);
	while(n>0){
		printf("%d\n",n);
		n--;
	}
	 return 0;
	}

     
	#include<stdio.h>
	 int main(){
		{
	        // block 1  n
	     }
	     
	     {
	     	// block 2   n^2
	     }
	     {
	     	 // block 3   1
	     }
	 return 0;
	}

	  for(i=0;i<n;i++) //  1st block
		{
		printf("hello world !");
	    }

       for(i=0;i<n;i++) // 2nd block
     {
          for(j=0;j<n;j++)
           {
              printf("hello world !");
           }
       }

		 for(i=0;i<n;i++) // 3rd block
		{
		    printf("hello world !");
		    if(i==2){
			break;
		       }
		 }

     for(i=1;i<n;i=i*2) // 4th block
             {
                   printf("hello world !");
                 }    

		  
     for(i=1;i<10;i++) // 5th block
	{
        printf("hello world !");
    }   

         
   j=0;
   for(i=0;i<n;i++) // 6th block
   {
         for(;j<n;j++)
       {
          printf("hello world !");
       }
   }
   

  void  merge(int a, int b, int low,int mid, int high)
  {
        // some O(n) operation
 }  
  void mergesort(int a, int b, int low, int high) // T(n)
       
       {

           int mid;
           if(low<high)
           {
               mid=(low+high)/2;      // O(1)
               mergesort(a,b,low,mid); // T(n/2)
               mergesort(a,b,mid+1,high); // T(n/2)
               merge(a,b,low,mid,high);  // O(n)
           }


       }