O(sqrt(N)) টাইম কমপ্লেক্সিটি

O(sqrt(N)) টাইম কমপ্লেক্সিটিকে বলা হয় স্কয়ার রুট টাইম কমপ্লেক্সিটি । ইনপুটের বৃদ্ধির সাপেক্ষে আমাদের প্রোগ্রামের অপারেশন যদি তার বর্গমূলের / রুটের সমান হয় সেই কমপ্লেক্সিটি কে আমরা বলতেছি স্কয়ার রুট টাইম কমপ্লেক্সিটি বা O(sqrt(N)) টাইম কমপ্লেক্সিটি। যেমন ধরুন , আমাদের প্রোগ্রামে যদি এমন কোনো ইন্সট্রাকশন থাকে যা একটি ভ্যরিয়েবল ইনপুট N স্কয়ার রুটের / বর্গমুল কাছাকাছি কোন মান হয় অর্থাৎ N এর ভ্যালু ১০ হলে কাজটি কম বেশি $\sqrt{১০}$ ~ ৩ বার সম্পাদন হয় , N এর ভ্যালু ১০০ হলে কাজটি কম বেশি $\sqrt{১০০}$ ~ ১০ বার সম্পাদন হয় , N এর ভ্যালু ১০০০ হলে কাজটি কম বেশি $\sqrt{১০০০}$ ~ ৩১ বার সম্পাদন হয় সেই ক্ষেত্রে আমরা বলতে পারি , আমাদের কোডটির টাইম কমপ্লেক্সিটি O(sqrt(N)). খেয়াল করে দেখবেন , এইক্ষেত্রে আমাদের কোডের টাইম কমপ্লেক্সিটি এনালাইসিস পদ্ধতি আগের মডিউলের টাইম কমপ্লেক্সিটি O(N) এর সাথে কিছু টা মিল রয়েছে। চলুন ,কিছু কোডের উদাহরণ দেখে বিষয়টি আরো ভালোভাবে বুঝার চেষ্টা করি । Problem 1 :

    int n ; cin >> n ;
    
    for(int i =1 ;i<=sqrt(n) ;i++){
       if(n%i==){
          cout << i << " " ;
          cout << n/i << " " ;
          }
    }
    
    Input : 100 
    Output : 100 50 25 12 6 3 

উপরোক্ত কোডটি হলো কোন একটি নাম্বারের গুণনীয়ক বের করার জন্য ব্যবহার করা হয়। এখানে দেখুন , আমরা মেইন লুপটি ১ থেকে শুরু করে ঐ নাম্বার N এর স্কয়ার রুট পর্যন্ত চেক করতেছি। তাইলে , এই লুপটি ইনপুট N=১০ এর জন্য $\sqrt{১০}$ ~ ৩ বার , ইনপুট ১০০ এর জন্য $\sqrt{১০০}$ ~ ১০ বার এবং $\sqrt{১০০০}$ ~ ৩১ বার চলবে। যেহেতু এটি একটি ইনপুট N এর জন্য ম্যাক্সিমাম তার স্কয়ার রুট পর্যন্ত চলছে, তাই এই কোডের টাইম কমপ্লেক্সিটি হলো O(sqrt(N)) Problem 2 :

    int i = 1 , s = 1 ;
    
    while(s<n){
       s = s + i ;
       i++ ;
   }

আমরা কিছু উদাহরণের সাহায্যে দেখার চেষ্টা করবো এই কোড এর ইম্পরট্যান্ট পার্ট টুকু অর্থাৎ লুপটি N এর বিভিন্ন ইনপুটের জন্যে কীভাবে কাজ করছে।

প্রথমে N এর মান ১০ এর জন্য চেক করে দেখি।

	s	s+i
1	1	1+1 = 2 ( ১বার)
2	1+1	1+1+2= 4 (২ বার)
3	1+1+2	1+1+2+3 =7 (৩ বার)
4	1+1+2+3	1+1+2+3+4 = 11 >10

এখানে দেখা যাচ্ছে N এর মান ১০ এর জন্য লুপটি ৩ বার চলবে। যা ১০ এর স্কয়ার রুট এর সমান অর্থাৎ $\sqrt{১০}$ ~ ৩ এর সমান।

উপরে যদি আমরা লক্ষ্য করি s এর মান এর সাথে i এর মান শেষ পর্যন্ত কত যোগ করার পরে s এর মান N এর থেকে ছোট থাকতেছে ঠিক সেই পরিমান ই লূপ টি চলছে। আমরা ধরে নিই k ই হচ্ছে সবচেয়ে বড় সংখ্যা যা s er সাথে যোগ হতে পারবে যাতে করে s এর মান N থেকে ছোট থাকে / সমান হয়।

Mathematical Explanation

উপরে আমরা দেখেছি , K এর মান ম্যক্সিমাম হতে পারে স্কয়ার রুট N পর্যন্ত । এখন হয়তো মনে আসতে পারে , এই ছোট ফ্যাক্টর গুলা কি কোন ইফেক্ট ফেলবে না ? এই লুপ টা আমরা চালালে N এর ভ্যালু ১০০ এর জন্য ১৪ বার চলবে যা exactly ১০০ এর বর্গমূল থেকে ৪ বেশি। সুতারাং এই হাতে গুনা কিছু ইটারেশন বেশি হলে ঐ বিষয়টি আমরা কমপ্লেক্সিটি তে include করি না। Overall ম্যক্সিমাম স্কয়ার রুট N এর থেকে কিছু বেশি বা কম হতে পারে।

তাই উক্ত কোডের টাইম কমপ্লেক্সিটি হবে O(sqrt(n)).

সহজে মনে রাখার উপায়ঃ যখন আমাদের কোডে লুপের কন্ডিশন ০/১ থেকে শুরু হয়ে স্কয়ার রুট N পর্যন্ত চলে অথবা আমাদের আমাদের লুপের কন্ডিশন এর ভ্যারিয়েবল এমন ভাবে বাড়তে থাকে যে তা ১ থেকে শুরু করে কোন একটি নির্দিষ্ট স্বাভাবিক ংখ্যার যোগফল আকারে বাড়তে থাকে তবে এই ক্ষেত্রে আমরা বলতে পারি এই কোডের টাইম কমপ্লেক্সিটি হলো O(sqrt(N))। বেশি বেশি কোড দেখতে দেখতে এই টাইম কমপ্লেক্সিটি কীভাবে বের করতে হবে তা আমরা জানতে পারবো।