# O(logN) টাইম কমপ্লেক্সিটি

O(logN) টাইম কমপ্লেক্সিটিকে বলা হয় লগারিদমিক টাইম কমপ্লেক্সিটি । ইনপুটের বৃদ্ধির সাপেক্ষে আমাদের প্রোগ্রামের অপারেশন যদি  একটি  নির্দিষ্ট বেস এর লগারিদমিক  হারে কমতে থাকে সেই কমপ্লেক্সিটি কে আমরা বলতেছি লগারিদমিক টাইম কমপ্লেক্সিটি বা O(lognN) টাইম কমপ্লেক্সিটি। যেমন ধরুন , আমাদের প্রোগ্রামে যদি এমন কোনো ইন্সট্রাকশন থাকে যা একটি ভ্যরিয়েবল ইনপুট N এর লগারিদমিক মান এর উপর নির্ভর করে অর্থাৎ N  এর ভ্যালু ১০ হলে কাজটি কম বেশি  log10 \~ ৩  বার সম্পাদন হয় , N এর ভ্যালু ১০০ হলে কাজটি  কম বেশি  log100 \~ 6 বার সম্পাদন হয় , N এর ভ্যালু ১০০০ হলে কাজটি  কম বেশি  log1000 \~ 9 বার সম্পাদন হয় সেই ক্ষেত্রে আমরা বলতে পারি , আমাদের কোডটির টাইম কমপ্লেক্সিটি O(logN). খেয়াল করে দেখবেন , এইক্ষেত্রে আমাদের কোডের টাইম কমপ্লেক্সিটি আগের মডিউলের টাইম কমপ্লেক্সিটি O(N) এর মতো ইনপুটের সাথে সাথে সমান হারে বাড়ছে না।  \
\
চলুন ,কিছু কোডের উদাহরণ দেখে বিষয়টি আরো ভালোভাবে বুঝার চেষ্টা করি ।\
\
**Problem 1** :&#x20;

```cpp
    int n ; cin >> n ;
    
    for(int i =N ;i>1 ;i= i/2 ){
    cout << i << endl ;
    }
    
    Input : 100 
    Output : 100 50 25 12 6 3 

```

&#x20;চলেন , উপরের কোডে লুপ টি কয়বার চলবে তা আমরা একটি উদাহরণের সাহায্যে দেখার চেষ্টা করি। ধরেন , N এর মান ১০০। প্রথমে লুপ ১০০ (১ নং) থেকে শুরু হবে , এরপর ১০০/২ = ৫০ (২ নং)  -> ৫০/২ = ২৫ (৩ নং)  -> ২৫/২ = ১২ (৪ নং) -> ১২/২ = ৬ (৫ নং)  -> ৬/২ = ৩  (৬ নং) -> ৩/২ = ১ , এখানে  লুপ টি থেমে যাবে।  দেখা যাচ্ছে এখানে সর্বমোট ৬ বার লুপ টি চলেছে। দেখা যাচ্ছে ১০০ কে ২ দিয়ে যতবার ভাগ করা যাচ্ছে ঠিক তত সংখ্যক বার লুপটি চলছে। আর একটি সংখ্যা N কে ২ দিয়ে কতবার ভাগ করা যাবে তা আমরা প্রকাশ করি logN  দ্বারা। তাই এই কোডের টাইম কমপ্লেক্সিটি হলো O(logN).  \
\
**Problem 2 :**&#x20;

```cpp
    int n ; cin >> n ;

    for(int i =1 ;i<n ;i=i*2){
        cout << i << endl ;
    } 

    Input : 100 
    Output : 1 4 8 16 32 64
```

কিছু উদাহরণের সাহায্যে আমরা N এবং এই কোডের লুপ সংখ্যার সাথে তা বের করার চেষ্টা  করবো। ধরেন N এর মান হলো ১০। এখন i =1 থেকে শুরু হবে , 1\*2 = 2 (১ বার)  -> 2\*2-> 4  (২ বার) -> 4\*2 -> 8 (৩ বার)  , 8\*2 = 16> 10 , লুপটি এখানে থেমে যাবে। সুতারাং সর্বমোট log10 \~3 বার এই লুপটি চলেছে । এরপর আসেন ,  N এর মান ১০০ এর জন্য টেস্ট করে দেখি বিষয়  টি। i =1 , থেকে শুরু হবে এরপর  1\*2 = 2 (১ বার)  -> 2\*2-> 4  (২ বার) -> 4\*2 -> 8 (৩ বার)  , 8\*2 = 16 (4 বার) ->  16\*2 -> 32 (৫ বার) -> 32\*2 = 64 (৬ বার) -> 64\*2=128>100 এখানে লুপটি থেমে যাবে। সুতারাং সর্বমোট log100 \~6 বার লুপটি চলেছে। সবশেষে এখান থেকে আমরা বুঝতে পারতেছি যে কোন একটি সংখ্যা কে ম্যাক্সিমাম কয়বার ২ দিয়ে গুণ করা যাবে যাতে করে তা N এর থেকে ছোট হয় / সমান হয় , তা হলো ঐ সংখ্যার লগের সমান অর্থাৎ logN এর সমান । তাই উপরের কোডের টাইম কমপ্লেক্সিটি হচ্ছে O(logN). \
\
**Problem 3  :**&#x20;

```cpp
    k=2 ;
    for(int i =0 ;i<n ;i++){
        i*=k ;
    }
```

উপরের কোড এ আমাদের মনে হতে পারে , লুপটি তে যেহেতু i এর মান ০ থেকে শুরু হয়ে N এর আগ পর্যন্ত যাচ্ছে এবং  প্রত্যেক ক্ষেত্রে i++ হচ্ছে তাই হয়তো এর কমপ্লেক্সিটি O(N) এর সমান। কিন্তু ভিতরের ইন্সট্রাকশন এ লক্ষ্য করলে দেখা যায় , সেখানে i এর মানের সাথে প্রত্যেকবার 2 গুণ হচ্ছে। এবং উপরের প্রবলেম থেকে জেনে এসেছি ,  কোন একটি সংখ্যা কে ম্যাক্সিমাম কয়বার ২ দিয়ে গুণ করা যাবে যাতে করে তা N এর থেকে ছোট হয় / সমান হয় , তা হলো ঐ সংখ্যার লগের সমান অর্থাৎ logN এর সমান। তাই এই কোডের টাইম কমপ্লেক্সিটি হবে O(logN).\


**সহজে মনে রাখার উপায়ঃ** \
\
যখন আমাদের কোডে কোন একটি লুপের key variable যেমন  i  এর মান যদি দিগুন হারে বাড়তে থাকে অথবা i এর মান প্রতিক্ষেত্রে অর্ধেক হয়ে কমতে থাকে , সেই ক্ষেত্রে আমরা বলতে পারি আমাদের কোডের টাইম কমপ্লেক্সিটি হলো O(logN)&#x20;
