টাইম কমপ্লেক্সিটির কিছু উদাহরন

এবার আমরা কিছু উদাহরন থেকে টাইম কমপ্লেক্সিটি বের করার চেষ্টা করি।

উদাহরন ১ঃ

for(int i=0;i<N;i++)     // একটি লুপ চলছে ০ থেকে N পর্যন্ত -> কমপ্লেক্সিটি O(N)
    {
        x++;
    }
    for(int i=0;i<M;i++)    // একটি লুপ চলছে ০ থেকে M পর্যন্ত -> কমপ্লেক্সিটি O(M)
    {
        y++;
    }
                           // টোটাল কমপ্লেক্সিটি O(N) + O(M)  [ কারন দুটি লুপ আলাদাভাবে চলছে ]

উদাহরন ২ঃ

int a=0;
    for(int i=0;i<N;i++)      // একটি লুপ চলছে ০ থেকে N পর্যন্ত -> কমপ্লেক্সিটি O(N)
    {
        for(int j=N;j>i;j--)     // একটি লুপ চলছে N থেকে i পর্যন্ত -> কমপ্লেক্সিটি O(N) [ worst কেসে i যখন ০ হয়ে যাবে তখন লুপটি পুরো N থেকে ০ পর্যন্ত চলবে। ]
        {
            a = a+i+j;
        }
    }
                             // টোটাল কমপ্লেক্সিটি O(N) * O(N) = O(N*N)  [ কারন একটি লুপ আরেকটি লুপের ভিতরে আছে নেস্টেড আকারে ]

উদাহরন ৩ঃ

int i,j,k=0;
    for(i = n/2;i<=n;i++)      // একটি লুপ চলছে n/2 থেকে n পর্যন্ত -> কমপ্লেক্সিটি O(N/2) = O(N) [ আমরা কন্সট্যান্ট বাদ দিয়ে কমপ্লেক্সিটি বের করি ]
    {
        for(j=2;j<=n;j*=2)    // একটি লুপ চলছে 2 থেকে n পর্যন্ত এবং প্রতিবার দ্বিগুণ হচ্ছে -> কমপ্লেক্সিটি O(log2N) = O(logN) [ আমরা কন্সট্যান্ট বাদ দিয়ে কমপ্লেক্সিটি বের করি ]
        {
            k = k+n/2;
        }
    }
                             // টোটাল কমপ্লেক্সিটি O(N) * O(logN) = O(NlogN)  [ কারন একটি লুপ আরেকটি লুপের ভিতরে আছে নেস্টেড আকারে ]

উদাহরন ৪ঃ

    int n = 20;                    // ১টি অপারেশন -> কমপ্লেক্সিটি O(1)
    int sum = (n*(n+1))/2;         // ১টি অপারেশন -> কমপ্লেক্সিটি O(1)
    if(sum%2 == 0)                 // ১টি অপারেশন -> কমপ্লেক্সিটি O(1)
    { 
        cout << "EVEN";            // ১টি অপারেশন -> কমপ্লেক্সিটি O(1)
    }
    else
    {
        cout << "ODD";            // ১টি অপারেশন -> কমপ্লেক্সিটি O(1)
    }
                                  // টোটাল কমপ্লেক্সিটি O(1)

উদাহরন ৫ঃ

 for(int i=0;i<n;i++)          // একটি লুপ চলছে ০ থেকে N পর্যন্ত -> কমপ্লেক্সিটি O(N)
    {
        for(int j=0;j<n;j++)          // একটি লুপ চলছে ০ থেকে N পর্যন্ত -> কমপ্লেক্সিটি O(N)
        {
            for(int k=0;k<n;k++)          // একটি লুপ চলছে ০ থেকে N পর্যন্ত -> কমপ্লেক্সিটি O(N)
            {
                cout << i+j+k << endl;         
            }
        }
    }


    for(int j=0;j<n;j++)          // একটি লুপ চলছে ০ থেকে N পর্যন্ত -> কমপ্লেক্সিটি O(N)
    {
        for(int k=0;k<n;k++)          // একটি লুপ চলছে ০ থেকে N পর্যন্ত -> কমপ্লেক্সিটি O(N)
        {
            cout << i+j+k << endl;         
        }
    }

                           //  টোটাল কমপ্লেক্সিটি O(N*N*N) + O(N*N) = O(N*N*N)  [ কমপ্লেক্সিটি ক্যালকুলেট করার সময় আমরা সবচেয়ে বড় ভেলুটি নেই। এখানে N^3 বড় N^2 এর চেয়ে ]

উদাহরন ৬ঃ

    int i=1;
    while(i<n)             // প্রথম while লুপটি ১ থেকে n পর্যন্ত চলছে। 
    {
        int j=n;           
        while(j>0)         // দ্বিতীয় while লুপটি n থেকে ১ পর্যন্ত চলছে। 
        {
            j = j/2;       //  দ্বিতীয় while লুপটি n থেকে ১ পর্যন্ত চলছে এবং প্রতিবার ২ দিয়ে ভাগ হচ্ছে -> কমপ্লেক্সিটি O(logN)
        }
        i = i*2;          // প্রথম while লুপটি ১ থেকে n পর্যন্ত চলছে এবং i এর মান প্রতিবার দ্বিগুণ হচ্ছে -> কমপ্লেক্সিটি O(logN)
    }  

                          //  টোটাল কমপ্লেক্সিটি O(logN) * O(logN) = O((logN)*(logN))

উদাহরন ৭ঃ

    for(int i=0;i<n;i++)        // একটি লুপ চলছে ০ থেকে N পর্যন্ত -> কমপ্লেক্সিটি O(N)
    {
        for(int j=0;j<m;j++)      // একটি লুপ চলছে ০ থেকে M পর্যন্ত -> কমপ্লেক্সিটি O(M)
        {
            cout << i*j << endl;
        }
    }
                             //  টোটাল কমপ্লেক্সিটি O(N) * O(M) = O(N*M)

উদাহরন ৮ঃ

    for(int i=0;i<n/2;i++)        // একটি লুপ চলছে 0 থেকে n/2 পর্যন্ত -> কমপ্লেক্সিটি O(N/2) = O(N) [ আমরা কন্সট্যান্ট বাদ দিয়ে কমপ্লেক্সিটি বের করি ]
    {
        for(int j=1; j+n/2<=n; j++)    // একটি লুপ চলছে 1 থেকে n/2 পর্যন্ত -> কমপ্লেক্সিটি O(N/2) = O(N)
        {
            for(int k=1;k<=k;k*=2)        // একটি লুপ চলছে 1 থেকে n পর্যন্ত এবং প্রতিবার দ্বিগুণ হচ্ছে -> কমপ্লেক্সিটি O(logN)
            {
                cout << "Phitron";
            }
        }
    }

                                  //  টোটাল কমপ্লেক্সিটি O(N) * O(N) * O(logN) = O(N*N*logN)