project.cpp

/*
  PROJECT FOR THE END-SEM
  COMPLEXITY ANALYSIS OF AN ALGORITHM BASEDON DIFFERENT TEST CASES
  1 )  BASIC IDEA  :  AN ALGORITHM WOULD BE TESTED ON VARIOUS TEST CASES BASED ON DIFFERENT INPUT SIZES

*/

#include <bits/stdc++.h>
using namespace std ;
map<int,string> m ;
double processor_unit_time ;
double observed_time ;
const int MAXN = 1e6 ;
 vector<int>a( MAXN ) ;
#define FOR(i, n) for (int i = 0; i < n; i++)
int n, t[4*MAXN];
#define ff first
#define ss second
int cnt[ 50 ] ;
void build ( int v, int tl, int tr) {
	if (tl == tr)
		t[v] = a[tl];
	else {
		int tm = (tl + tr) / 2;
		build (v*2+1 , tl, tm);
		build (v*2+2, tm+1, tr);
		t[v] = t[v*2 + 1] + t[v*2+2];
	}
}

void Complexity_calculator (  double  N  )
  {
       double mi = 1e9 ;
       int idx  ;
       double T[11] ;

       T[1] = N*processor_unit_time ; //  O( N ) complexity
       T[2] = N*log2(N)*processor_unit_time  ; // O( N*log2(N) )
       T[3] = N*N*processor_unit_time  ; // O( N*N )
       T[4] = N*N*log2(N)*processor_unit_time;  // O(N*N*log2(N))
       T[5] = log2(N)*processor_unit_time  ;
       T[6] = N*N*N*processor_unit_time ;
       T[7] = N*N*N*N*processor_unit_time ;
       T[8] = sqrt(N)*processor_unit_time ;
       T[9] = sqrt(N)*N*processor_unit_time ;
       T[10] = N*N*sqrt( N )*processor_unit_time ;

       for( int i = 1 ; i <= 10 ; i ++ )
         {
            T[i]  = T[i];
            cout<<T[i]<<endl ;
            if( abs(T[i] - observed_time) < mi )
              {
                 mi =  abs(T[i] - observed_time) ;
                 idx = i ;
              }
         }

         cout<<m[idx]<<endl;

  }

 void Complexity_calculator (  double  N , double observed_time  )
  {
       double mi = 1e9 ;
       int idx  ;
       double T[12] ;

       T[1] = N*processor_unit_time ; //  O( N ) complexity
       T[2] = N*log2(N)*processor_unit_time  ; // O( N*log2(N) )
       T[3] = N*N*processor_unit_time  ; // O( N*N )
       T[4] = N*N*log2(N)*processor_unit_time;  // O(N*N*log2(N))
       T[5] = log2(N)*processor_unit_time  ;
       T[6] = N*N*N*processor_unit_time ;
       T[7] = N*N*N*N*processor_unit_time ;
       T[8] = sqrt(N)*processor_unit_time ;
       T[9] = sqrt(N)*N*processor_unit_time ;
       T[10] = N*N*sqrt( N )*processor_unit_time ;
       T[11] = N*log2(log2(N))*processor_unit_time  ; // O( N*log2(N) )
       for( int i = 1 ; i <= 11 ; i ++ )
         {
            T[i]  = T[i];
           // cout<<T[i]<<endl ;
            if( abs(T[i] - observed_time) < mi )
              {
                 mi =  abs(T[i] - observed_time) ;
                 idx = i ;
              }
         }

         cnt[idx]++  ;
        // cout<<m[idx]<<endl;

  }

void  pre( )
  {


   const clock_t begin_time = clock();
   for( int i = 1 ; i <= MAXN ; i ++ ) ;
   double k =  float( clock () - begin_time ) /  CLOCKS_PER_SEC;
   processor_unit_time  =  k/MAXN ;

     m[ 1 ] = "O(N)" ;
     m[ 2 ] = "O( N* Log(N) )" ;
     m[ 3 ] = "O( N^2 )"  ;
     m[ 4 ] = "O( N^2 * Log(N) )" ;
     m[ 5 ] = "O( Log(N) )" ;
     m[ 6 ] = "O( N^3 ) " ;
     m[ 7 ] = "O( N^4 ) " ;
     m[ 8 ] = "O( sqrt(N) )" ;
     m[ 9 ] = "O( N * sqrt(N) )" ;
     m[ 10 ] = "O( N^2 * sqrt(N) ) ";
     m[ 11 ] = "O( N* Log(log(N) )" ;

  }
int main(  )
 {
   //  int n ;
   freopen("Seive_NLOGN.out", "r", stdin);
   vector<pair<double,double> > A( 1000 );
   FOR( i, 1000 )cin>>A[i].ff>>A[i].ss ;
   pre() ;
   FOR( i , 1000 )
     Complexity_calculator( A[i].ff , A[i].ss ) ;

   int  ma = 0 ;
   int maidx = 0 ;
   FOR( i , 12 )
     {
       if( cnt[i] > cnt[maidx] )
            maidx = i ;
       cout<<" "<<cnt[i]<<" " << m[i]<<endl ;
     }


  /*
   int N = 10001 ;

  const clock_t b_time2 = clock();

   for( int i = 1 ; i <= N ; i ++ )
     for( int j = 1 ; j <= sqrt(N) ;  j++  )
      {
         ;
      }

     double  k =  float( clock () - b_time2 ) /  CLOCKS_PER_SEC;


    printf("%.8f\n",k) ;
    observed_time  = k ;
    cout<<'\n';



    Complexity_calculator( N ) ;


    for( int i = 0 ; i < N ; i ++ )a[i] = rand()%N ;

    const clock_t b3 = clock() ;
    //sort(a.begin(),a.end() )  ;
    build(  0 , 0 , N - 1 ) ;
    observed_time  =   float( clock () - b3 ) /  CLOCKS_PER_SEC;
    cout<<observed_time<<endl ;
    pre() ;
    Complexity_calculator( N ) ;

   */

 }