🚀 DSA জার্নি: টাইম এবং স্পেস কমপ্লেক্সিটি (Time & Space Complexity)

ডেটা স্ট্রাকচার এবং অ্যালগরিদম (DSA) শেখার প্রথম এবং সবথেকে গুরুত্বপূর্ণ ধাপ হলো অ্যালগরিদম অ্যানালাইসিস করা। এই রিপোজিটরিতে আমি টাইম এবং স্পেস কমপ্লেক্সিটি নিয়ে আমার বিস্তারিত লার্নিং নোটস শেয়ার করছি।

📌 টাইম কমপ্লেক্সিটি (Time Complexity) কি?

টাইম কমপ্লেক্সিটি মানে এই নয় যে কোড রান হতে কত সেকেন্ড সময় লাগছে। বরং, ইনপুট সাইজ ($n$) বাড়ার সাথে সাথে অ্যালগরিদমটি রান হতে কেমন সময় নেবে, তার গাণিতিক হারকে টাইম কমপ্লেক্সিটি বলে।

কমন টাইম কমপ্লেক্সিটি নোটেশনসমূহ:

১. $O(1)$ - কনস্ট্যান্ট টাইম (Constant Time)

ইনপুট যাই হোক না কেন, কাজ সবসময় একই সময়ে শেষ হয়।

int a = 10, b = 20;
int sum = a + b; // এটি সবসময় O(1)

২. $O(\log n)$ - লগারিদমিক টাইম (Logarithmic Time)

প্রতি ধাপে ইনপুট অর্ধেক হয়ে যায়। এটি অত্যন্ত দ্রুত।

for (int i = n; i > 1; i = i / 2) {
    cout << i; // এটি O(log n)
}

৩. $O(n)$ - লিনিয়ার টাইম (Linear Time)

ইনপুট যত বাড়বে, সময়ও ঠিক ততটুকুই বাড়বে। একটি লুপ থাকলে এমন হয়।

for (int i = 0; i < n; i++) {
    cout << i; // n বার চলবে
}

৪. $O(n \log n)$ - লিনিয়ারিথমিক টাইম (Linearithmic Time)

একটি $n$ বারের লুপের ভেতর যদি প্রতিবার $\log n$ কাজ হয়। সর্টিং অ্যালগরিদমে (Merge Sort) এটি দেখা যায়। সহজ কথায়, এটি $O(n)$ এবং $O(\log n)$ এর গুণফল।

// বাইরের লুপটি n বার চলে -> O(n)
for (int i = 0; i < n; i++) {

    // ভেতরের লুপটি প্রতিবার অর্ধেক হয়ে যাচ্ছে -> O(log n)
    for (int j = n; j > 1; j = j / 2) {
        cout << "Working...";
    }
}

এখানে টোটাল কমপ্লেক্সিটি হবে $n \times \log n = O(n \log n)$।

৫. $O(n^2)$ - কোয়াড্রাটিক টাইম (Quadratic Time)

লুপের ভেতর লুপ থাকলে (Nested Loop) এমন হয়। ইনপুট দ্বিগুণ হলে সময় চারগুণ বেড়ে যায়।

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cout << i << j; // n * n বার চলবে
    }
}

6. Cubic Time Complexity — $O(n^3)$

এটি মূলত নেস্টেড লুপের ভেতর নেস্টেড লুপ। অর্থাৎ ৩টি লুপ একে অপরের ভেতরে থাকবে।

for (int i = 0; i < n; i++) {           // ১ম লুপ (n বার)
    for (int j = 0; j < n; j++) {       // ২য় লুপ (n বার)
        for (int k = 0; k < n; k++) {   // ৩য় লুপ (n বার)
            cout << i << j << k;
        }
    }
}

• হিসাব: $n \times n \times n = n^3$
• কখন হয়? সাধারণ ম্যাট্রিক্স গুণন (Matrix Multiplication) এর বেসিক অ্যালগরিদমে এটি দেখা যায়। এটি খুব স্লো, তাই $n$ এর মান বড় হলে (যেমন $n=1000$) কম্পিউটার হ্যাং করতে পারে!

7. Time Complexity with Two Variables — $O(n \times k)$

সব সময় যে ইনপুট শুধু একটাই ($n$) হবে তা কিন্তু নয়। কখনো কখনো আপনার কোড দুটি আলাদা ইনপুটের ওপর নির্ভর করে।

উদাহরণ: ধরুন আপনার কাছে $n$ সংখ্যক ছাত্র আছে এবং প্রতিটি ছাত্রের $k$ টি করে সাবজেক্ট আছে। আপনি সবার সব সাবজেক্ট প্রিন্ট করবেন।

void printGrades(int n, int k) {
    for (int i = 0; i < n; i++) {       // n বার চলে
        for (int j = 0; j < k; j++) {   // k বার চলে
            cout << "Student " << i << " Subject " << j;
        }
    }
}

• হিসাব: এখানে ভেতরের লুপটি $n$ এর ওপর নয়, বরং $k$ এর ওপর নির্ভর করছে। তাই এটি $O(n \times k)$।
• ভুল করবেন না: এটাকে $O(n^2)$

⚖️ ক্যালকুলেশন করার সহজ নিয়ম

1. যোগের নিয়ম (Addition): যদি আলাদা আলাদা লুপ থাকে: O(n) + O(n) = O(2n) -> O(n) (কনস্ট্যান্ট ২ বাদ যাবে)।

2. গুণের নিয়ম (Multiplication): লুপের ভেতর লুপ থাকলে: n * n = O(n^2)।

3. বড় পাওয়ার রাখা: যদি রেজাল্ট হয় O(n^2 + n + 1), আমরা শুধু বড়টি রাখব: O(n^2)।

💾 স্পেস কমপ্লেক্সিটি (Space Complexity)

কোড রান করার সময় মেমোরিতে (RAM) অতিরিক্ত কতটুকু জায়গা লাগছে সেটাই স্পেস কমপ্লেক্সিটি।

• O(1) Space: যদি শুধু ২-৩টি ভেরিয়েবল ব্যবহার করি।
• O(n) Space: যদি ইনপুট $n$ সাইজের একটি অ্যারে (Array) ডিক্লেয়ার করি।

**অ্যালগরিদমগুলোর মধ্যে Binary Search হলো অন্যতম সেরা একটি উদাহরণ যা খুব দ্রুত কাজ করে। চলুন সহজভাবে বুঝি কেন এটি $O(\log n)$: **

1. কাজের পদ্ধতি (Divide and Conquer) বাইনারি সার্চের মূল আইডিয়া হলো প্রতিবার চেক করার পর আমরা ডেটাসেট বা অ্যারেটিকে অর্ধেক (Half) করে ফেলি।
   • ধরুন আপনার কাছে ১০০টি এলিমেন্ট আছে।
   • প্রথমবার চেক করার পর যদি কাঙ্ক্ষিত ভ্যালুটি না পান, তবে আপনি বাকি ৫০টি বাদ দিয়ে দিচ্ছেন।
   • এরপর ২৫টি, তারপর ১২টি… এভাবে খুব দ্রুত আপনি আপনার টার্গেটে পৌঁছে যান।
2. গাণিতিক হিসাবধরি আমাদের কাছে $n$ সংখ্যক এলিমেন্ট আছে এবং $k$ বার সার্চ করার পর আমরা ভ্যালুটি খুঁজে পেলাম। যেহেতু প্রতিবার আমরা ২ দিয়ে ভাগ করছি, তাই:

\(\frac{n}{2^k} = 1\) \((n = 2^k)\)

এখানে উভয় পাশে Log নিলে আমরা পাই: \(\log_2(n) = k\)

অর্থাৎ, আমরা $n$ কে কতবার ২ দিয়ে ভাগ করলে ১-এ পৌঁছাবো? উত্তর হলো $\log_2 n$ বার। একারণেই টাইম কমপ্লেক্সিটি $O(\log n)$।

• বাইনারি সার্চের জন্য একটিই শর্ত—অ্যারে অবশ্যই Sorted (সাজানো) হতে হবে। অগোছালো অ্যারেতে এটি কাজ করবে না।

Big-O ($O$): The Upper Bound (সর্বোচ্চ সীমা)

Big-O নির্দেশ করে একটি অ্যালগরিদম সর্বোচ্চ কত সময় নিতে পারে (Worst Case)। এটি আমাদের গ্যারান্টি দেয় যে, “ভাই, এই কোডটা রান হতে এর চেয়ে বেশি সময় আর লাগবে না।”

• উদাহরণ: আপনি যদি বলেন একটি কাজ শেষ করতে আপনার সর্বোচ্চ ১০ মিনিট লাগবে, তবে আপনি ৫ মিনিটে করলেও সমস্যা নেই, কিন্তু ১০ মিনিটের বেশি যেন না হয়। এটাই $O$।

Big-Theta ($\Theta$): The Tight Bound (একদম সঠিক সীমা)

Big-Theta হলো আরও বেশি সুনির্দিষ্ট। এটি নির্দেশ করে যে অ্যালগরিদমটি সবসময় একটি নির্দিষ্ট সীমার মধ্যেই কাজ করবে। এটি Upper Bound এবং Lower Bound দুটোর সমন্বয়।

• উদাহরণ: যদি আপনার কোনো কাজ করতে সবসময় ঠিক ৮ থেকে ১০ মিনিটই লাগে, তবে সেটা হলো $\Theta$। এটি কাজের গড়পড়তা বা আসল পরিস্থিতির সঠিক চিত্র দেয়।

একটি বাস্তব উদাহরণ দিয়ে পার্থক্য বুঝুন:

ধরুন আপনার কাছে একটি অ্যারে আছে এবং আপনি সেখানে একটি সংখ্যা খুঁজছেন (Linear Search):

• Big-O ($O$): আমরা বলতে পারি এই সার্চের কমপ্লেক্সিটি $O(n)$। এর মানে হলো সর্বোচ্চ $n$ বার লুপটি ঘুরবে। (যদিও ১ বার চেক করেও সংখ্যাটি পাওয়া যেতে পারে, কিন্তু $O(n)$বলাটা ভুল নয় কারণ এটি সর্বোচ্চ সীমা বোঝাচ্ছে)।

• Big-Theta ($\Theta$): আপনি যখন বলবেন কমপ্লেক্সিটি $\Theta(n)$, তার মানে হলো অ্যালগরিদমটি ইনপুটের সাথে সাথে লিনিয়ারলিই বাড়ছে, এর কোনো ব্যতিক্রম নেই।

Big-Omega ($\Omega$)

Big-Omega নির্দেশ করে একটি অ্যালগরিদম রান হতে কমপক্ষে বা সর্বনিম্ন (Best Case) কতটুকু সময় নেবে। এটি হলো অ্যালগরিদমের Lower Bound।

• সহজ উদাহরণ: আপনি যদি কাউকে বলেন, “এই কাজটা করতে আমার কমপক্ষে ৫ মিনিট লাগবে।” এর মানে হলো কাজটা ৫ মিনিটেও হতে পারে, বা তার বেশি (১০ বা ২০ মিনিট) লাগতে পারে, কিন্তু কখনোই ৫ মিনিটের কম লাগবে না। এটাই ($\Omega$)।

• Big-O ($O$) Worst Case “সর্বোচ্চ কত সময় লাগবে?” (Upper Bound)
• Big-Omega ($\Omega$) Best Case “সর্বনিম্ন কত সময় লাগবে?” (Lower Bound) -Big-Theta ($\Theta$) Average Case “গড়পড়তা বা ঠিক কত সময় লাগবে?” (Tight Bound)

একটি বাস্তব উদাহরণ (Linear Search):

ধরা যাক, একটা অ্যারেতে আপনি একটি সংখ্যা খুঁজছেন।

• Best Case ($\Omega$): যদি কপাল ভালো থাকে, সংখ্যাটি একদম প্রথম ইনডেক্সেই পেয়ে যাবেন। তাহলে কমপ্লেক্সিটি হবে $\Omega(1)$।
• Worst Case ($O$): যদি কপাল খারাপ হয়, সংখ্যাটি একদম শেষে থাকবে। তখন কমপ্লেক্সিটি হবে $O(n)$।

What is the time complexity of the best-known algorithm for matrix multiplication of two n×n matrices?

1. সাধারণ নিয়ম ($O(n^3)$):আমরা স্কুল-কলেজে যেভাবে ম্যাট্রিক্স গুণ করা শিখি (Row দিয়ে Column-কে গুণ), সেই পদ্ধতিতে দুটি $n \times n$ ম্যাট্রিক্স গুণ করলে আমাদের ৩টি নেস্টেড লুপ লাগে। তাই এর টাইম কমপ্লেক্সিটি হয় $O(n^3)$।

2. স্ট্র্যাসেন অ্যালগরিদম (Strassen’s Algorithm):১৯৬৯ সালে ভলকার স্ট্র্যাসেন দেখান যে, ম্যাট্রিক্স গুণন $O(n^3)$ এর চেয়েও দ্রুত করা সম্ভব। তিনি একটি বিশেষ গাণিতিক ট্রিক ব্যবহার করে গুণের সংখ্যা কমিয়ে আনেন। তার অ্যালগরিদমের কমপ্লেক্সিটি ছিল প্রায় $O(n^{2.81})$।

3. বর্তমান সেরা রেকর্ড ($O(n^{2.373})$):স্ট্র্যাসেনের পর অনেক গণিতবিদ এটি আরও কমানোর চেষ্টা করেছেন। বর্তমানে সবথেকে পরিচিত এবং দ্রুততম অ্যালগরিদমটি হলো Coppersmith–Winograd algorithm (এবং এর আধুনিক ভার্সনগুলো), যার কমপ্লেক্সিটি প্রায় $O(n^{2.373})$।

Amortized Complexity আসলে কী?

সহজ ভাষায়: কোনো একটি কাজে মাঝে মাঝে অনেক বেশি সময় লাগে, কিন্তু বেশিরভাগ সময় সেটি খুব দ্রুত হয়ে যায়। এই “বেশি সময়” লাগার খরচটা যখন অন্য সব “দ্রুত হওয়া” কাজের ওপর ভাগ করে দেওয়া হয়, তখন তাকে Amortized সময় বলে।

বাস্তব উদাহরণ: Dynamic Array (যেমন Vector বা ArrayList)

ধরুন আপনার কাছে একটি অ্যারে আছে যার সাইজ ৪। আপনি এতে ৪টি এলিমেন্ট ইনসার্ট করলেন খুব দ্রুত ($O(1)$ সময়)।

• ১. ১ম ইনসার্ট: $O(1)$
• ২. ২য় ইনসার্ট: $O(1)$
• ৩. ৩য় ইনসার্ট: $O(1)$
• ৪. ৪র্থ ইনসার্ট: $O(1)$
• ৫. ৫ম ইনসার্ট: এখন তো জায়গা নেই! কম্পিউটার এখন কী করবে? সে মেমোরিতে নতুন একটি ৮ সাইজের অ্যারে বানাবে এবং আগের ৪টি এলিমেন্ট কপি করে সেখানে নেবে। এই কাজটিতে অনেক বেশি সময় লাগবে ($O(n)$)।

কিন্তু এই $O(n)$ কাজটা কি সবসময় হয়? না, এটি খুব কম সময়ে একবার হয়।

কেন এটি Average Case নয়?

• Average Case: এখানে আমরা ধরে নিই ইনপুটগুলো র‍্যান্ডম (Random) হতে পারে।

• Amortized Analysis: এখানে আমরা নিশ্চিত যে, একটা সিকোয়েন্স বা ধারাবাহিক অপারেশনের পর গড় খরচ সব সময় কমই হবে। যেমন: ডাইনামিক অ্যারেতে আপনি $n$ সংখ্যক ডেটা পুশ করলে গড় খরচ সব সময় $O(1)$ Amortized-ই হবে।

Worst-Caseএকবারে সর্বোচ্চ কত সময় লাগতে পারে (যেমন রি-সাইজের সময় $O(n)$)।

Amortizedঅনেকগুলো অপারেশন শেষে গড়পড়তা কত সময় লাগল (গ্যারান্টিড $O(1)$)।

What is the space complexity of a recursive function that makes n recursive calls in total, with no additional data structures, where each call adds one frame to the call stack?

এটি একটি অত্যন্ত গুরুত্বপূর্ণ কনসেপ্ট, কারণ অনেক সময় আমরা মনে করি কোডে কোনো অ্যারে বা ভেক্টর না থাকলে স্পেস কমপ্লেক্সিটি $O(1)$ হবে। কিন্তু Recursion-এর ক্ষেত্রে বিষয়টি আলাদা।

কেন এটি $O(n)$ হবে?

• যখন একটি ফাংশন নিজেকে কল করে (Recursive Call), তখন কম্পিউটার সেই ফাংশনের জন্য মেমোরিতে একটি জায়গা বরাদ্দ করে, যাকে বলা হয় Stack Frame।

• ১. আপনি যখন ১ম বার কল করলেন, একটি ফ্রেম স্ট্যাকে জমা হলো।
• ২. সেই ফাংশন থেকে যখন ২য় কল হলো, ১ম ফ্রেমটি কিন্তু শেষ হয়নি, বরং তার ওপর ২য় ফ্রেমটি জমা হলো।
• ৩. এভাবে $n$ বার কল করলে স্ট্যাকে একটার ওপর একটা মোট $n$ টি স্ট্যাক ফ্রেম জমা হবে।

গাণিতিক হিসেব:

• প্রতিটি স্ট্যাক ফ্রেমে কিছু লোকাল ভেরিয়েবল এবং রিটার্ন অ্যাড্রেস থাকে (যা একটি Constant Space)।

• যদি প্রতিটি ফ্রেমের সাইজ $C$ হয়, তবে $n$ টি ফ্রেমের জন্য মোট জায়গা লাগবে:\(n \times C = O(n)\)

একটি উদাহরণ দিয়ে বুঝুন:

ধরা যাক, ১ থেকে $n$ পর্যন্ত সংখ্যার যোগফল বের করার একটি রিকার্সিভ ফাংশন:

int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1); // এখানে নতুন কল হচ্ছে
}

যদি $n = 5$ হয়, তবে মেমোরিতে sum(5), sum(4), sum(3), sum(2), sum(1) এবং sum(0) — এই সবগুলোর জন্য আলাদা জায়গা লাগবে যতক্ষণ না শেষ কলটি তার রেজাল্ট ফেরত পাঠাচ্ছে। তাই এখানে স্পেস কমপ্লেক্সিটি $O(n)$।

গুরুত্বপূর্ণ নোট (Tail Recursion): কিছু আধুনিক কম্পাইলার Tail Recursion Optimization ব্যবহার করে এই স্পেস কমিয়ে $O(1)$-এ নিয়ে আসতে পারে, কিন্তু সাধারণ ক্ষেত্রে এবং ইন্টারভিউতে উত্তর সব সময় $O(n)$-ই ধরা হয়।

Cubic Time Complexity

for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        for(int k=0; k<n; k++){
            sum +=arr[i][j][k];
        }
    }
}

লুপের বিশ্লেষণ:

কোডটিতে ৩টি নেস্টেড লুপ (একটির ভেতরে আরেকটি) আছে:সবচেয়ে বাইরের লুপ (i):

• এটি $0$ থেকে $n-1$ পর্যন্ত চলে, অর্থাৎ মোট $n$ বার।
• মাঝখানের লুপ (j): বাইরের লুপের প্রতি ১ বার ঘোরার জন্য এই লুপটি $n$ বার চলে।

• সবচেয়ে ভেতরের লুপ (k): মাঝখানের লুপের প্রতি ১ বার ঘোরার জন্য এই লুপটি আবার $n$ বার চলে।

• গাণিতিক হিসাব:মোট কাজের সংখ্যা বের করতে আমাদের ৩টি লুপের গুণফল নিতে হবে:\(Total\ Operations = n \times n \times n = n^3\)তাই বিগ-ও নোটেশনে একে বলা হয় $O(n^3)$।

এটি কি ফাস্ট নাকি স্লো?

এটি বেশ স্লো (Slow) কমপ্লেক্সিটি।

• যদি $n = 10$ হয়, তবে কাজ হবে $1,000$ বার।যদি $n = 1,000$ হয়, তবে কাজ হবে $1,000,000,000$ (১০০ কোটি!) বার।
• সাধারণত প্রোগ্রামিং কন্টেস্টে $n$-এর মান ৫০০-এর বেশি থাকলে $O(n^3)$ সলিউশন সাবমিট করলে TLE (Time Limit Exceeded) আসার সম্ভাবনা থাকে।

for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
            arr[i][j]=0;
    }
}

কেন এটি $O(n \times m)$?

এখানে দুটি আলাদা ইনপুট বা ভেরিয়েবল কাজ করছে:

• বাইরের লুপ (i): এটি চলে $0$ থেকে $n-1$ পর্যন্ত, অর্থাৎ মোট $n$ বার।
• ভেতরের লুপ (j): বাইরের লুপের প্রতিটি ধাপের জন্য এই লুপটি চলে $0$ থেকে $m-1$ পর্যন্ত, অর্থাৎ মোট $m$ বার।

যেহেতু একটি লুপের ভেতর আরেকটি লুপ আছে, তাই মোট কাজের সংখ্যা হবে তাদের গুণফল:\(Total\ Operations = n \times m\)তাই বিগ-ও নোটেশনে এটি $O(n \times m)$।

int i=n;
while(i>1){
    i=i/2
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(\log n)$ (Logarithmic Time Complexity)।

কেন এটি $O(\log n)$?

সহজভাবে বললে, প্রতিবার লুপটি চলার সময় ইনপুট $i$ এর মান অর্ধেক হয়ে যাচ্ছে। ধরা যাক, $n = 16$:

• ১ম ধাপ: $i = 16 / 2 = 8
• $২য় ধাপ: $i = 8 / 2 = 4$
• ৩য় ধাপ: $i = 4 / 2 = 2$
• ৪র্থ ধাপ: $i = 2 / 2 = 1$
• ৫ম ধাপ: $i = 1$ (লুপের শর্ত i > 1 আর সত্যি নয়, তাই লুপ বন্ধ হবে)

খেয়াল করুন, ইনপুট ১৬ হলেও লুপ চলেছে মাত্র ৪ বার। গণিতের ভাষায়, $2^4 = 16$। অর্থাৎ ১৬ কে কতবার ২ দিয়ে ভাগ করলে ১ পাওয়া যায়? উত্তর হলো $\log_2 16 = 4$ বার।

গাণিতিক বিশ্লেষণ

• যদি লুপটি $k$ বার চলে, তবে $k$ ধাপ পর $i$ এর মান হবে $\frac{n}{2^k}$।
• লুপটি থামবে যখন $\frac{n}{2^k} \approx 1$ হবে।
• এখান থেকে পাই: $n = 2^k$
• উভয় পাশে Log নিলে: $k = \log_2 n$তাই সময় লাগছে $O(\log n)$।

for(int i=0; i<n; i++){
    for(int j=0; j<n; j=j*2){
            sum++;
    }
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n \log n)$।

লুপ দুটির বিশ্লেষণ

• বাইরের লুপ (i): এটি 0 থেকে শুরু করে n-1 পর্যন্ত যাচ্ছে এবং প্রতিবার ১ করে বাড়ছে (i++)। এটি একটি সাধারণ লিনিয়ার লুপ, যা মোট $n$ বার চলবে।

• ভেতরের লুপ (j): এই লুপটি শুরু হচ্ছে 1 থেকে এবং প্রতিবার ২ দিয়ে গুণ হয়ে বাড়ছে (j = j * 2)। আমরা জানি, যে লুপ গুণ বা ভাগের মাধ্যমে লাফিয়ে চলে তার কমপ্লেক্সিটি হয় $\log n$। সুতরাং এই লুপটি প্রতিবার $\log n$ বার চলবে।

মোট টাইম কমপ্লেক্সিটি

যেহেতু একটি লুপের ভেতরে আরেকটি লুপ আছে, তাই মোট কাজের পরিমাণ হবে লুপ দুটির গুণফল:

বাস্তব উদাহরণ

এই $O(n \log n)$ কমপ্লেক্সিটিটি আপনি সবচেয়ে বেশি দেখবেন দক্ষ সর্টিং অ্যালগরিদমগুলোতে, যেমন: Merge Sort বা Quick Sort। এটি $O(n^2)$ এর চেয়ে অনেক বেশি ফাস্ট কিন্তু $O(n)$ এর চেয়ে কিছুটা স্লো।

void func(int n){
    if(n<=1)return;
    func(n/2);
    func(n/2);
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n)$।

এটি একটি রিকার্সিভ ফাংশন যা দেখে শুরুতে অনেকেরই মনে হতে পারে যে এটি $O(\log n)$ হবে (যেহেতু $n$ কে ২ দিয়ে ভাগ করা হচ্ছে)। কিন্তু এখানে একটি ট্রিক আছে। চলুন রিকার্সন ট্রি (Recursion Tree) দিয়ে বিষয়টি সহজে বুঝি:

১. রিকার্সন ট্রি বিশ্লেষণ

ফাংশনটি প্রতিটি ধাপে ২ ভাগে ভাগ হচ্ছে এবং ২ বার নিজেকে কল করছে।

• লেভেল ০: শুরুতে আমাদের কাছে আছে $n$ সাইজের একটি প্রবলেম।
• লেভেল ১: ফাংশনটি ২টি নতুন কল তৈরি করছে, যাদের প্রতিটির সাইজ $n/2$।
• লেভেল ২: ওই ২টি কলের প্রতিটি আবার ২টি করে (মোট ৪টি) কল তৈরি করছে, যাদের সাইজ $n/4$।

২. গাণিতিক হিসাব

আমরা যদি মোট কলের সংখ্যা হিসেব করি: \(Total\ Calls = 1 + 2 + 4 + 8 + \dots + n\)

এটি একটি জ্যামিতিক ধারা (Geometric Series)। এই ধারার যোগফল হলো প্রায় $2n - 1$।

বিগ-ও নোটেশনে আমরা কনস্ট্যান্ট (যেমন ২) বাদ দেই, তাই এটি দাঁড়ায় $O(n)$।

৩. মাস্টার থিওরেম (Master Theorem) প্রয়োগ

অ্যাডভান্সড লেভেলে এই ধরনের ইকুয়েশন সলভ করতে মাস্টার থিওরেম ব্যবহার করা হয়:\(T(n) = 2T(n/2) + O(1)\)

এখানে:

• $a = 2$ (প্রতি ধাপে কয়টি কল হচ্ছে)
• $b = 2$ (ইনপুট কত দিয়ে ভাগ হচ্ছে)
• $f(n) = O(1)$ (অতিরিক্ত কাজ কতটুকু)

যেহেতু $\log_b a = \log_2 2 = 1$ এবং $f(n)$ এর পাওয়ার ০, তাই মাস্টার থিওরেমের ১ম কেস অনুযায়ী কমপ্লেক্সিটি হয় $O(n^{\log_2 2}) = O(n^1) = O(n)$।

for(int i=1; i<=n; i++){
    for(int j=1; j<=i*i; j++){
            sum++;
    }
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n^3)$।

১. লুপের কাজের পরিমাণ বের করা

এখানে ভেতরের লুপটি ($j$) বাইরের লুপের ইনডেক্স $i$ এর ওপর নির্ভর করছে।

• যখন $i = 1$, $j$ চলবে $1^2 = 1$ বার।
• যখন $i = 2$, $j$ চলবে $2^2 = 4$ বার।
• যখন $i = 3$, $j$ চলবে $3^2 = 9$ বার।
• যখন $i = n$, $j$ চলবে $n^2$ বার।

২. গাণিতিক হিসাব (Sum of Squares)

মোট কাজের সংখ্যা বের করতে আমাদের এই বর্গের ধারাটি (Series of Squares) যোগ করতে হবে:

আমরা জানি, প্রথম $n$ সংখ্যক স্বাভাবিক সংখ্যার বর্গের যোগফলের সূত্র হলো:\(Sum = \frac{n(n+1)(2n+1)}{6}\)

৩. কেন এটি $O(n^3)$?

আমরা যদি উপরের ইকুয়েশনটিকে গুণ করি:

বিগ-ও নোটেশনের নিয়ম অনুযায়ী:

• আমরা কনস্ট্যান্ট বা ধ্রুবক (এখানে $\frac{1}{6}$) বাদ দিই।
• আমরা শুধুমাত্র সবথেকে বড় পাওয়ারটি রাখি। এখানে $n^3$ হলো সবথেকে বড় ঘাত।

প্রো-টিপ:

যদি আপনার বাইরের লুপ $n$ পর্যন্ত চলে এবং ভেতরের লুপ $i^k$ পর্যন্ত চলে, তবে তার কমপ্লেক্সিটি সাধারণত $O(n^{k+1})$ হয়। এখানে $k=2$ ছিল, তাই উত্তর হয়েছে $O(n^{2+1}) = O(n^3)$।

for(int i=1; i<=n; i=i*3){
    for(int j=1; j<=n; j++){
            sum++;
    }
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n \log_3 n)$, যা বিগ-ও নোটেশনে সাধারণত $O(n \log n)$ হিসেবে লেখা হয়।

১. লুপ দুটির বিশ্লেষণ

• বাইরের লুপ (i): লুপটি i = i * 3 ভাবে বাড়ছে। এর মানে প্রতি ধাপে $i$ এর মান ৩ গুণ হচ্ছে। এটি একটি লগারিদমিক লুপ। যেহেতু এটি ৩ এর পাওয়ার হিসেবে বাড়ছে, তাই এটি মোট $\log_3 n$ বার চলবে।

• ভেতরের লুপ (j): এটি একটি সাধারণ লিনিয়ার লুপ যা ১ থেকে $n$ পর্যন্ত প্রতিটি সংখ্যা চেক করে। তাই এটি প্রতিবার $n$ বার চলবে।

২. মোট টাইম কমপ্লেক্সিটি

একটি লুপের ভেতরে আরেকটি লুপ থাকলে আমরা তাদের কাজের পরিমাণ গুণ করি:

যেহেতু বিগ-ও নোটেশনে লগারিদমের বেস (২, ৩ বা ১০) খুব একটা প্রভাব ফেলে না (সবগুলোই একে অপরের কনস্ট্যান্ট মাল্টিপল), তাই একে সাধারণভাবে $O(n \log n)$ বলা হয়। ___

int i=0;
while(i<n){
    int j=n;
    while(j>0){
        j = j/2;
    }
    i++
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n \log n)$।

১. লুপ দুটির বিশ্লেষণ

• বাইরের লুপ (i): এটি i = 0 থেকে শুরু করে n-1 পর্যন্ত যাচ্ছে এবং প্রতিবার ১ করে বাড়ছে (i++)। এটি একটি সাধারণ লিনিয়ার লুপ, যা মোট $n$ বার চলবে।

• ভেতরের লুপ (j): এই লুপটি শুরু হচ্ছে j = n থেকে এবং প্রতিবার ২ দিয়ে ভাগ হয়ে কমছে (j = j / 2)। আমরা জানি, যে লুপ গুণ বা ভাগের মাধ্যমে লাফিয়ে চলে তার কমপ্লেক্সিটি হয় $\log n$। সুতরাং এই লুপটি প্রতিবার $\log n$ বার চলবে।

২. মোট টাইম কমপ্লেক্সিটি

যেহেতু একটি লুপের ভেতরে আরেকটি লুপ আছে, তাই মোট কাজের পরিমাণ হবে লুপ দুটির গুণফল: \(Total\ Time = (Outer\ Loop\ Iterations) \times (Inner\ Loop\ Iterations)\)

HashMap <Integer, List<Integer>>map=new HashMap<>();
for(int i=0; i<n; i++){
  List<Integer> list = new ArrayList<>();
  for(int j=0; j<n; j++){
    list.add(j);
  }
  map.put(i,list);
}

এই কোডটির স্পেস কমপ্লেক্সিটি হলো $O(n^2)$।

মেমোরি বিশ্লেষণ

১. বাইরের গঠন (HashMap):

আপনি একটি HashMap তৈরি করছেন যেখানে $n$ টি কী (Key) থাকবে। সুতরাং, ম্যাপের কীগুলোর জন্য জায়গা লাগছে $O(n)$।

২. ভেতরের গঠন (ArrayLists):

লুপের প্রতিটি ধাপে (মোট $n$ বার), আপনি একটি করে নতুন ArrayList তৈরি করছেন। প্রতিটি লিস্টের ভেতর আবার $n$ টি করে এলিমেন্ট রাখছেন।

• ১টি লিস্টের সাইজ = $n$
• মোট লিস্টের সংখ্যা = $n$
• সব লিস্ট মিলিয়ে মোট এলিমেন্টের সংখ্যা = $n \times n = n^2$

মোট স্পেস কমপ্লেক্সিটি হিসাব:

বিগ-ও ($O$) নোটেশনের নিয়ম অনুযায়ী, আমরা বড় পাওয়ারটি রাখি। তাই ফাইনাল রেজাল্ট হলো $O(n^2)$।

৩. একটি বাস্তব উদাহরণ (Graph Representation):

এই ধরনের ডেটা স্ট্রাকচার সাধারণত গ্রাফ থিওরিতে Adjacency List তৈরির সময় ব্যবহৃত হয়। যদি একটি গ্রাফের $n$ টি নোড থাকে এবং প্রতিটি নোড বাকি সব নোডের সাথে কানেক্টেড থাকে (Complete Graph), তবে সেটির মেমোরি খরচ হবে $O(n^2)$।

for(int i=1; i*i<=n; i++){
    print(i);
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(\sqrt{n})$ (Square Root of $n$)।

এটি একটি অত্যন্ত স্মার্ট লুপ কন্ডিশন, যা আমরা সাধারণত কোনো সংখ্যার Primality Testing (সংখ্যাটি মৌলিক কি না) বা Divisors (উৎপাদক) বের করার সময় ব্যবহার করি। চলুন দেখি কেন এটি $\sqrt{n}$ হলো।

১. লুপের বিশ্লেষণ

লুপের শর্তটি হলো: $i \times i \le n$।

একে অন্যভাবে লেখা যায়: $i \le \sqrt{n}$।

অর্থাৎ, লুপটি ১ থেকে শুরু হয়ে ততক্ষণ পর্যন্ত চলবে যতক্ষণ $i$ এর মান $\sqrt{n}$ এর সমান বা ছোট থাকে।

গাণিতিক হিসাব

লুপটি যদি $k$ বার চলে, তবে শর্ত অনুযায়ী:

সুতরাং, মোট কাজের পরিমাণ বা টাইম কমপ্লেক্সিটি হলো $O(\sqrt{n})$।

কমপ্লেক্সিটির তুলনা:

• $O(1)$ < $O(\log n)$ < $O(\sqrt{n})$ < $O(n)$

$O(\sqrt{n})$ লিনিয়ার টাইম ($O(n)$) এর চেয়ে অনেক বেশি দ্রুত কিন্তু লগারিদমিক টাইম ($O(\log n)$) এর চেয়ে কিছুটা ধীর।

for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        break;
    }
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n)$।

কেন এটি $O(n)$?

• ১. বাইরের লুপ (i): এটি $0$ থেকে $n-1$ পর্যন্ত চলে, অর্থাৎ মোট $n$ বার ঘুরবে।
• ২. ভেতরের লুপ (j): এই লুপটি শুরু হওয়ার সাথে সাথেই break কমান্ড পাচ্ছে। এর মানে হলো, j এর মান $0$ হওয়ার পর লুপটি আর সামনে এগোয় না এবং সাথে সাথে বন্ধ হয়ে যায়। ফলে ভেতরের লুপটি প্রতিবার মাত্র ১ বার কাজ করে।

গাণিতিক হিসাব:

মোট কাজের সংখ্যা = (বাইরের লুপের পুনরাবৃত্তি) $\times$ (ভেতরের লুপের পুনরাবৃত্তি)

তাই বিগ-ও নোটেশনে এটি $O(n)$।

void foo(int n){
    if(n<=1) return;
    foo(n/2);
    for(int i=0; i<n; i++){
        print(i)
    }
    foo(n/2);
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n \log n)$।

এটি একটি অত্যন্ত ক্লাসিক রিকার্সিভ প্যাটার্ন যা আমরা সাধারণত Merge Sort বা এই জাতীয় Divide and Conquer অ্যালগরিদমে দেখে থাকি। চলুন রিকার্সন ট্রি ব্যবহার করে এর গভীরে যাওয়া যাক:

১. কোডটির বিশ্লেষণ

এই ফাংশনটি মূলত তিনটি কাজ করছে:

• নিজেকে একবার কল করছে অর্ধেক ইনপুট নিয়ে: foo(n / 2)
• একটি লিনিয়ার লুপ চালাচ্ছে যা $n$ বার চলে: $O(n)$
• নিজেকে আবার কল করছে অর্ধেক ইনপুট নিয়ে: foo(n / 2)

এর রিকারেন্স রিলেশনটি হবে:

২. রিকার্সন ট্রি (Recursion Tree) দিয়ে বোঝা

আপনি যদি কল্পনা করেন এই ফাংশনটি কীভাবে ছড়িয়ে পড়ছে:

• লেভেল ০: একটি কাজ হচ্ছে যার সাইজ $n$। লুপটি চলছে $n$ বার।
• লেভেল ১: দুটি কাজ হচ্ছে যাদের প্রতিটির সাইজ $n/2$। মোট লুপ চলছে $(\frac{n}{2} + \frac{n}{2}) = n$ বার।
• লেভেল ২: চারটি কাজ হচ্ছে যাদের প্রতিটির সাইজ $n/4$। মোট লুপ চলছে $(\frac{n}{4} \times 4) = n$ বার।

প্রতিটি লেভেলে মোট কাজের পরিমাণ কিন্তু $n$ ই থাকছে। এখন প্রশ্ন হলো, কতগুলো লেভেল আছে? যেহেতু $n$ প্রতিবার অর্ধেক হচ্ছে, তাই মোট লেভেল আছে $\log_2 n$ টি।

৩. মোট হিসাব

৪. মাস্টার থিওরেম (Master Theorem) প্রয়োগ

যদি আপনি সরাসরি সূত্র দিয়ে করতে চান:

এখানে $a = 2$, $b = 2$, এবং $f(n) = n^1$।

যেহেতু $\log_b a = \log_2 2 = 1$, যা $f(n)$-এর পাওয়ারের সমান, এটি মাস্টার থিওরেমের ২য় কেস। তাই রেজাল্ট হবে $O(n^1 \log n)$।

for(int i=0; i<n; i++){
    for(int j=0; j<n; i++){
        for(int k=j; k<n; k++){
            sum++;
        }
    }
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n^3)$।

১. লুপের গঠন বিশ্লেষণ

• সবচেয়ে বাইরের লুপ (i): এটি $0$ থেকে $n-1$ পর্যন্ত চলে। অর্থাৎ এটি মোট $n$ বার ঘোরে।

• ভেতরের দুই লুপ (j এবং k): এই অংশটুকু একটু ট্রিকি।
• যখন $j=0$, তখন $k$ চলে $n$ বার।
• যখন $j=1$, তখন $k$ চলে $n-1$ বার।
• যখন $j=n-1$, তখন $k$ চলে $1$ বার।

এই ভেতরের দুটি লুপের মোট কাজের পরিমাণ হলো একটি গাণিতিক ধারা (Arithmetic Progression):

এটি মূলত $O(n^2)$ এর সমান।

২. মোট টাইম কমপ্লেক্সিটি হিসাব

এখন আমাদের কাছে আছে:

• বাইরের লুপের জন্য $n$
• ভেতরের লুপদ্বয়ের জন্য $\frac{n^2+n}{2}$

সব মিলিয়ে মোট কাজের পরিমাণ:

বিগ-ও নোটেশনের নিয়ম অনুযায়ী, আমরা কনস্ট্যান্ট ($1/2$) এবং ছোট ঘাত ($n^2$) বাদ দিয়ে শুধুমাত্র সবথেকে বড় ঘাতটি গ্রহণ করি। তাই রেজাল্ট দাঁড়ায় $O(n^3)$।

void solve(int n){
    if(n <=1) return;
    for(int i=0; i<n; i++){
        print(i)
    }
    solve(n/3)
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n)$।

এটি একটি রিকার্সিভ ফাংশন যার ভেতরে একটি লুপ রয়েছে। এটি কেন $O(n)$ হলো, তা বুঝতে আমাদের প্রতিটি রিকার্সন লেভেলে কতটুকু কাজ হচ্ছে তা যোগ করতে হবে।

১. কাজের বিশ্লেষণ (Step-by-Step)

ফাংশনটি প্রতিটি ধাপে নিচের কাজগুলো করছে:

• একটি লুপ চালাচ্ছে যা বর্তমান $n$ এর সমান বার ঘোরে।
• এরপর নিজেকে কল করছে $n/3$ ইনপুট দিয়ে।

চলুন দেখি মোট কতবার print হচ্ছে:

• ১ম কল: $n$ বার কাজ হয়।
• ২য় কল: $n/3$ বার কাজ হয়।
• ৩য় কল: $n/9$ বার কাজ হয়।
• … এভাবে যতক্ষণ না $n \le 1$ হয়।

২. গাণিতিক হিসাব

মোট কাজের পরিমাণ হলো একটি অসীম গুণোত্তর ধারা (Infinite Geometric Series) এর যোগফল (তাত্ত্বিকভাবে):

আমরা যদি $n$ কমন নেই:

এই ধারার যোগফলের সূত্র $\frac{a}{1-r}$ ব্যবহার করলে আমরা পাই:

৩. বিগ-ও ($O$) ফলাফল

যেহেতু $1.5$ একটি কনস্ট্যান্ট বা ধ্রুবক, তাই বিগ-ও নোটেশনে আমরা একে বাদ দেই। ফলে চূড়ান্ত টাইম কমপ্লেক্সিটি দাঁড়ায়: $O(n)$

সহজ টেকনিক:

যদি দেখেন একটি রিকার্সিভ ফাংশনে ইনপুট ভাগ হচ্ছে (যেমন $n/2, n/3$) এবং সেই ফাংশনের ভেতরে একটি লিনিয়ার লুপ ($O(n)$) আছে যা প্রতিবার কমছে, তবে সেই পুরো কোডের কমপ্লেক্সিটি সাধারণত লিনিয়ার বা $O(n)$ ই থাকে। কারণ প্রথম কলের কাজই সবথেকে বেশি, পরের কলগুলোর কাজ এতই দ্রুত কমে যে সেগুলো যোগ করলেও প্রথম কলের দ্বিগুণ হতে পারে না।

for(int i=0; i<n; i++){
    for(int j=0; j<n; i++){
        c[i][j]=0;
        for(int k=0; k<n; k++){
            c[i][j]+=a[i][k]*b[k][j]
        }
    }
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n^3)$।

এটি একটি অত্যন্ত সুপরিচিত অ্যালগরিদম—Matrix Multiplication (ম্যাট্রিক্স গুণফল)। চলুন বিশ্লেষণ করে দেখি কেন এটি $O(n^3)$ হলো:

১. লুপের গঠন বিশ্লেষণ

এই কোডটিতে তিনটি নেস্টেড (একটির ভেতর আরেকটি) লুপ রয়েছে:

1. সবচেয়ে বাইরের লুপ (i): এটি $0$ থেকে $n-1$ পর্যন্ত চলে, অর্থাৎ এটি মোট $n$ বার ঘোরে। এটি রেজাল্ট ম্যাট্রিক্সের প্রতিটি ‘রো’ (row) নির্দেশ করে।
2. মাঝখানের লুপ (j): এটিও $0$ থেকে $n-1$ পর্যন্ত চলে, অর্থাৎ এটিও মোট $n$ বার ঘোরে। এটি প্রতিটি ‘কলাম’ (column) নির্দেশ করে।
3. সবচেয়ে ভেতরের লুপ (k): এটিও $0$ থেকে $n-1$ পর্যন্ত চলে, অর্থাৎ এটিও মোট $n$ বার ঘোরে। এটি মূলত ডট প্রোডাক্ট (dot product) করার জন্য প্রতিটি এলিমেন্টের গুণ এবং যোগ সম্পন্ন করে।

২. গাণিতিক হিসাব

যেহেতু লুপগুলো একে অপরের ভেতরে অবস্থান করছে, তাই মোট কাজের পরিমাণ হবে লুপগুলোর গুণফল:

বিগ-ও নোটেশনে একে আমরা লিখি $O(n^3)$।

৩. ভিজ্যুয়ালাইজেশন

কল্পনা করুন একটি ঘনক (Cube) যার দৈর্ঘ্য, প্রস্থ এবং উচ্চতা প্রতিটিই $n$। ম্যাট্রিক্স গুণের ক্ষেত্রে প্রতিটি সেলের মান বের করার জন্য আমাদের পুরো একটি রো এবং একটি কলামের ওপর দিয়ে যেতে হয়, যা এই কিউবিক কমপ্লেক্সিটি তৈরি করে।

int power(int base, int exp){
    if (exp == 0 ) return 1;
    if(exp % 2 ==0)
        return power(base * base, exp / 2 )
    else
        return base * power (base, exp - 1)
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(\log \text{exp})$।

• এটি একটি অত্যন্ত দক্ষ অ্যালগরিদম, যাকে বলা হয় Binary Exponentiation বা Exponentiation by Squaring। সাধারণ লুপ দিয়ে পাওয়ার বের করতে $O(\text{exp})$ সময় লাগে, কিন্তু এখানে সেটি অনেক দ্রুত ঘটে।

১. কেন এটি $O(\log \text{exp})$?

এই ফাংশনটির মূল শক্তি লুকিয়ে আছে exp / 2 অংশটিতে। প্রতিটি ধাপে আমরা এক্সপোনেন্ট বা পাওয়ারকে দুই ভাগে ভাগ করে দিচ্ছি।

• যখন exp জোড় সংখ্যা (Even), তখন আমরা পাওয়ারকে অর্ধেক করে দিচ্ছি: $base^{exp} = (base^2)^{exp/2}$।
• যখন exp বিজোড় সংখ্যা (Odd), তখন আমরা একটি বেস আলাদা করে পাওয়ারকে জোড় বানিয়ে নিচ্ছি: $base^{exp} = base \times base^{exp-1}$।

যেহেতু আমরা বেশিরভাগ ধাপে ইনপুটকে ২ দিয়ে ভাগ করছি, তাই এটি একটি Logarithmic প্রসেস।

২. একটি উদাহরণের মাধ্যমে দেখা যাক:

ধরা যাক আমরা $2^{10}$ বের করতে চাই:

• power(2, 10) -> জোড়, তাই power(4, 5)
• power(4, 5) -> বিজোড়, তাই $4 \times$ power(4, 4)
• power(4, 4) -> জোড়, তাই power(16, 2)
• power(16, 2) -> জোড়, তাই power(256, 1)
• power(256, 1) -> বিজোড়, তাই $256 \times$ power(256, 0)
• power(256, 0) -> বেস কেস, রিটার্ন $1$।

এখানে exp = 10 কিন্তু ফাংশনটি মাত্র ৬টি ধাপে কাজ শেষ করেছে। ইনপুট যত বাড়বে, এই পার্থক্যের মাহাত্ম্য তত বাড়বে।

৩. স্পেস কমপ্লেক্সিটি:

এখানে রিকার্সন ব্যবহার করা হয়েছে। যেহেতু রিকার্সন স্ট্যাকের গভীরতাও লগারিদমিকভাবে বাড়ে, তাই এর স্পেস কমপ্লেক্সিটি হলো $O(\log \text{exp})$।

for(int i=0; i<n; i++){
    int x=i;
    while(x>0){
        x/=10;
    }
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n \log_{10} n)$।

এটি একটি অত্যন্ত ইন্টারেস্টিং প্যাটার্ন যেখানে বাইরের লুপটি লিনিয়ার হলেও ভেতরের লুপটি ইনপুটের মানের ওপর নির্ভর করছে। চলুন ধাপে ধাপে এর বিশ্লেষণ দেখি:

১. লুপ দুটির বিশ্লেষণ

• বাইরের লুপ ($i$): এটি $0$ থেকে শুরু করে $n-1$ পর্যন্ত প্রতিটি সংখ্যার জন্য একবার করে চলে। অর্থাৎ এটি মোট $n$ বার ঘোরে।

• ভেতরের লুপ ($while$): খেয়াল করুন, এই লুপটি প্রতিটি $i$-এর জন্য আলাদাভাবে চলে। এটি $i$-এর মানকে প্রতিবার ১০ দিয়ে ভাগ করছে যতক্ষণ না সেটি ০ হয়। কোনো সংখ্যাকে বারবার ১০ দিয়ে ভাগ করলে সেটি কতবার চলবে, তা নির্ভর করে ওই সংখ্যাটির অঙ্ক সংখ্যার (number of digits) ওপর।

• একটি সংখ্যা $x$-কে ১০ দিয়ে ভাগ করে ০-তে নামিয়ে আনতে গাণিতিকভাবে $\log_{10} x$ বার লুপ চালাতে হয়।

২. মোট টাইম কমপ্লেক্সিটি হিসাব

এখানে মোট কাজের পরিমাণ হবে প্রতিটি $i$-এর জন্য ভেতরের লুপের কাজের যোগফল:

লগারিদমের ধর্ম অনুযায়ী, $\log 1 + \log 2 + \dots + \log n = \log(n!)$। স্টার্লিংয়ের অ্যাপ্রোক্সিমেশন (Stirling’s Approximation) অনুযায়ী, $\log(n!)$ এর মান প্রায় $n \log n$ এর সমান।

তাই বিগ-ও ($O$) নোটেশনে আমরা পাই: $O(n \log_{10} n)$

সহজভাবে বোঝার উপায়:

ভেতরের লুপটি মূলত প্রতিটি সংখ্যার ডিজিট বা অঙ্ক সংখ্যা কাউন্ট করছে। যেহেতু $n$ পর্যন্ত প্রতিটি সংখ্যার গড় অঙ্ক সংখ্যা প্রায় $\log_{10} n$, তাই পুরো কাজটি করতে $n \times \log_{10} n$ সময় লাগছে।

boolean isPrime(int n){
    if (n<2) return false;
    for(int i=2; i*i <=n; i++){
        if(n%i==0) return false;
    }
    return true;
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(\sqrt{n})$।

১. কেন এটি $O(\sqrt{n})$?

লুপের কন্ডিশনটি খেয়াল করুন: i * i <= n। একে সহজ বীজগাণিতিক নিয়মে লিখলে দাঁড়ায়:

অর্থাৎ, লুপটি $2$ থেকে শুরু হয়ে সর্বোচ্চ $\sqrt{n}$ পর্যন্ত চলবে। যেহেতু লুপের ভেতরের কাজগুলো (ভাগশেষ চেক করা) ধ্রুবক সময়ের কাজ বা $O(1)$, তাই পুরো ফাংশনটির সময় নির্ভর করছে লুপটি কতবার ঘুরছে তার ওপর।

২. গাণিতিক যুক্তি (কেন $\sqrt{n}$ পর্যন্ত দেখলেই হয়?)

যদি $n$ একটি যৌগিক সংখ্যা হয়, তবে তার অন্তত একটি উৎপাদক (factor) $a$ থাকবে যা $1 < a \leq \sqrt{n}$ শর্তটি মেনে চলবে।

• উদাহরণস্বরূপ, $n = 36$ হলে এর $\sqrt{36} = 6$। এর উৎপাদকগুলো হলো: $(2, 18), (3, 12), (4, 9), (6, 6)$।

• খেয়াল করুন, প্রতিটি জোড়ার মধ্যে অন্তত একটি সংখ্যা $6$-এর সমান বা ছোট। তাই আমরা যদি $6$ পর্যন্ত কোনো উৎপাদক না পাই, তবে নিশ্চিতভাবেই বলা যায় $36$-এর ওপরের দিকেও কোনো উৎপাদক থাকবে না।

৩. কমপ্লেক্সিটি বিশ্লেষণ:

• Best Case: $O(1)$ (যদি $n$ একটি জোড় সংখ্যা হয় এবং ২ দিয়ে ভাগ যায়)।

• Worst Case: $O(\sqrt{n})$ (যদি $n$ একটি মৌলিক সংখ্যা হয়, তবে লুপটি পুরো $\sqrt{n}$ পর্যন্ত চলবে)। ___

  void permute(int[] arr, int l, int r) {
    if (l == r) { print(arr); return; }
    for (int i = l; i <= r; i++) {
        swap(arr[l], arr[i]);
        permute(arr, l + 1, r);
        swap(arr[l], arr[i]);
    }
  }
  

  এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n \times n!)$।

এটি একটি অত্যন্ত পরিচিত ব্যাকট্র্যাকিং (Backtracking) অ্যালগরিদম, যা দিয়ে একটি অ্যারের সব ধরনের পারমুটেশন (Permutation) বা বিন্যাস বের করা হয়। চলুন দেখি কেন এর কমপ্লেক্সিটি এত বেশি।

১. রিকার্সন ট্রি বিশ্লেষণ

একটি অ্যারের সাইজ যদি $n$ হয়, তবে তার মোট পারমুটেশন সংখ্যা হয় $n!$ (n factorial)।

• লেভেল ০ (রুট): আমাদের কাছে $n$ টি অপশন আছে।
• লেভেল ১: প্রতিটি অপশনের জন্য আমাদের কাছে আরও $(n-1)$ টি অপশন আছে।
• লেভেল ২: এরপর প্রতিটি অপশনের জন্য আরও $(n-2)$ টি অপশন আছে।
• … এভাবে চলতে থাকে।

এই রিকার্সন প্রক্রিয়ায় মোট লিফ নোড (Leaf nodes) বা শেষ ধাপের সংখ্যা হলো $n!$। অর্থাৎ ফাংশনটি মোট $n!$ বার শেষ পর্যায়ে পৌঁছায়।

২. কাজের হিসাব

টাইম কমপ্লেক্সিটি বের করার জন্য আমাদের দুটি জিনিস মাথায় রাখতে হবে:

• রিকার্সন কলের সংখ্যা: মোট রিকার্সিভ কল হয় প্রায় $e \times n!$ টি (যেখানে $e$ একটি কনস্ট্যান্ট)। সহজ কথায়, এটি $O(n!)$ এর সমান।
• প্রতিটি কলের ভেতরের কাজ: * প্রতিটি ধাপে একটি লুপ চলছে। সবচেয়ে গুরুত্বপূর্ণ হলো, যখন রিকার্সনটি একদম শেষ পর্যায়ে (l == r) পৌঁছায়, তখন আমরা পুরো অ্যারেটি Print করছি। একটি অ্যারে প্রিন্ট করতে $O(n)$ সময় লাগে।

৩. চূড়ান্ত কমপ্লেক্সিটি

যেহেতু আমরা $n!$ সংখ্যক বিন্যাস তৈরি করছি এবং প্রতিটি বিন্যাস প্রিন্ট করতে $O(n)$ সময় লাগছে, তাই মোট কমপ্লেক্সিটি দাঁড়ায়:

৪. বাস্তব উদাহরণ

যদি $n=10$ হয়:

• $10! = 3,628,800$
• $n \times n! = 10 \times 3,628,800 = 36,288,000$ অপারেশন। এটি এখনো কম্পিউটারে ১ সেকেন্ডের কম সময়ে চলবে। কিন্তু $n=15$ হলেই এটি বিলিয়ন ছাড়িয়ে যাবে, যা শেষ হতে অনেক সময় লাগবে।

void merge_sort(int[] arr, int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    merge_sort(arr, l, mid);
    merge_sort(arr, mid + 1, r);
    merge(arr, l, mid, r);  // uses O(n) temp array
}

$O(n!)$। তবে আরও নিখুঁতভাবে বললে এটি $O(n \times n!)$।

১. রিকার্সন ট্রি বিশ্লেষণ

এই ফাংশনটি একটি অ্যারের সব ধরনের Permutation (বিন্যাস) বের করে। যদি অ্যারেতে $n$ টি উপাদান থাকে, তবে মোট বিন্যাস সংখ্যা হয় $n!$ (n factorial)।

• লেভেল ০: শুরুতে আমাদের কাছে $n$ টি অপশন থাকে (লুপটি $n$ বার চলে)।

• লেভেল ১: প্রতিটি অপশনের জন্য আমরা ১টি এলিমেন্ট ফিক্স করে বাকি $(n-1)$ টি এলিমেন্টের জন্য ফাংশন কল করি।

• লেভেল ২: এরপর প্রতিটি কলের জন্য আরও $(n-2)$ টি অপশন থাকে।

এইভাবে রিকার্সনটি নিচে নামতে থাকে যতক্ষণ না একটি পূর্ণ বিন্যাস তৈরি হয়। এই রিকার্সন ট্রিতে মোট লিফ নোড (Leaf nodes) বা শেষ ধাপের সংখ্যা হলো $n!$।

২. কেন $O(n \times n!)$?

টাইম কমপ্লেক্সিটি হিসাব করার সময় দুটি বিষয় মাথায় রাখতে হয়:

• রিকার্সিভ কলের সংখ্যা: যা প্রায় $O(n!)$।

• প্রতিটি কলের কাজ: খেয়াল করুন, যখন রিকার্সনটি একদম শেষ পর্যায়ে (l == r) পৌঁছায়, তখন আমরা পুরো অ্যারেটি Print করছি। একটি $n$ সাইজের অ্যারে প্রিন্ট করতে $O(n)$ সময় লাগে।

তাই মোট সময় লাগে: $n! \times n$ অর্থাৎ $O(n \times n!)$। অপশনে যেহেতু $O(n!)$ আছে, তাই এটিই সঠিক ক্যাটাগরি।

৩. বাস্তব উদাহরণ

যদি আপনার অ্যারেতে ১০টি সংখ্যা থাকে ($n=10$):

• $n! = 3,628,800$ (সাড়ে ৩৬ লক্ষের বেশি অপারেশন!) যদি $n=15$ হয়, তবে এই কোডটি শেষ হতে সাধারণ কম্পিউটারে কয়েক দিন লেগে যেতে পারে। এই কারণেই ফ্যাক্টোরিয়াল কমপ্লেক্সিটির অ্যালগরিদমগুলো শুধুমাত্র ছোট ইনপুটের জন্য ব্যবহার করা হয়।

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j = j + i) {
        for (int k = 1; k <= n; k = k * 2) {
            sum++;
        }
    }
}

• Outer Loop ($i$): Runs $n$ times.

• Middle Loop ($j$): The number of iterations depends on $i$. It runs $\frac{n}{i}$ times.

• Inner Loop ($k$): This is a logarithmic loop, running $\log n$ times because $k$ doubles each iteration.

• Total Complexity: The summation $\sum_{i=1}^{n} \frac{n}{i} \log n$ simplifies to $n \log n \sum \frac{1}{i}$. Since the Harmonic Series $\sum \frac{1}{i}$ is $O(\log n)$, the total time complexity is $O(n \log^2 n)$.

int binarySearch(int[] arr, int target, int lo, int hi) {
    if (lo > hi) return -1;
    int mid = (lo + hi) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] > target)
        return binarySearch(arr, target, lo, mid - 1);
    return binarySearch(arr, target, mid + 1, hi);
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(\log n)$।

এটি একটি ক্লাসিক Binary Search অ্যালগরিদম। লিনিয়ার সার্চের মতো প্রতিটি এলিমেন্ট একে একে চেক না করে, এটি প্রতি ধাপে সার্চ এরিয়া বা খোঁজার জায়গা অর্ধেক করে ফেলে।

১. কেন এটি $O(\log n)$?

বাইনারি সার্চের মূল শক্তি হলো “Divide and Conquer” বা ভাগ করে জয় করার নীতি। চলুন দেখি এটি কীভাবে কাজ করে:

• ধরা যাক, আপনার অ্যারের সাইজ $n = 8$।
• ১ম ধাপের পর, সার্চ এরিয়া অর্ধেক হয়ে যায়: $n = 4$।
• ২য় ধাপের পর, এটি আবার অর্ধেক হয়: $n = 2$।
• ৩য় ধাপের পর, এটি হয়: $n = 1$ (এখানেই আমরা কাঙ্ক্ষিত মান পাই বা নিশ্চিত হই যে মানটি নেই)।

গাণিতিকভাবে, আমরা $n$ কে কতবার $2$ দিয়ে ভাগ করলে $1$ পাবো? উত্তরটি হলো $\log_2 n$

২. রিকার্সন ট্রি বিশ্লেষণ

যেহেতু এটি একটি রিকার্সিভ ফাংশন, প্রতিটি কল একটি নতুন স্ট্যাক তৈরি করে। কিন্তু এখানে মজার ব্যাপার হলো, প্রতিবার শুধুমাত্র একটি রিকার্সিভ কল কার্যকর হয় (হয় বাম দিকে, নাহয় ডান দিকে)। ফলে এটি মার্জ সর্টের মতো বিশাল কোনো ট্রি তৈরি করে না, বরং একটি সোজা লাইনের মতো নিচে নামে।

৩. সেরা এবং খারাপ পরিস্থিতি (Best vs Worst Case)

• Best Case: $O(1)$ - যদি আপনার target মানটি একদম প্রথমবারেই mid পজিশনে পাওয়া যায়।

• Worst Case: $O(\log n)$ - যদি মানটি অ্যারের একদম শেষে থাকে বা অ্যারেতে না থাকে।

for (int i = 2; i <= n; i++) {
    for (int j = 2; j * j <= i; j++) {
        if (i % j == 0) break;
    }
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n\sqrt{n})$ বা $O(n^{1.5})$।

এটি মূলত $2$ থেকে $n$ পর্যন্ত প্রতিটি সংখ্যা মৌলিক (Prime) কি না তা চেক করার একটি অ্যালগরিদম। চলুন এর গাণিতিক কারণটি দেখে নিই:

১. লুপগুলোর বিশ্লেষণ

• বাইরের লুপ ($i$): এটি $2$ থেকে $n$ পর্যন্ত চলে। অর্থাৎ এটি মোট $n$ বার ঘোরে।

• ভেতরের লুপ ($j$): এটি প্রতিটি $i$-এর জন্য $2$ থেকে শুরু করে $\sqrt{i}$ পর্যন্ত চলে (যেহেতু j * j <= i মানেই হলো $j \leq \sqrt{i}$)।

২. গাণিতিক হিসাব

মোট কাজের পরিমাণ বের করতে আমাদের প্রতিটি $i$-এর জন্য ভেতরের লুপটি কতবার চলছে তার যোগফল বের করতে হবে:

ক্যালকুলাসের ইন্টিগ্রেশন পদ্ধতি ব্যবহার করে এই ধারার যোগফল বের করলে দেখা যায়:

যেহেতু বিগ-ও ($O$) নোটেশনে আমরা কনস্ট্যান্ট বা ধ্রুবক ($\frac{2}{3}$) বাদ দিই, তাই চূড়ান্ত কমপ্লেক্সিটি দাঁড়ায়: $O(n\sqrt{n})$ বা $O(n^{1.5})$।

৩. সহজভাবে বোঝার উপায়

• বাইরের লুপটি চলছে $n$ বার।
• ভেতরের লুপটি গড়ে $\sqrt{n}$ বার চলছে।
• দুটির গুণফল $n \times \sqrt{n} = n^{1.5}$।

int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            if (i + j + k < n) count++;
            else break;
        }
    }
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n^3)$।

যদিও এখানে একটি break স্টেটমেন্ট আছে, যা দেখে মনে হতে পারে এটি কমপ্লেক্সিটি কমিয়ে দেবে, কিন্তু গাণিতিকভাবে এটি এখনো কিউবিক ($n^3$) ক্যাটাগরিতেই অবস্থান করছে। চলুন এর কারণগুলো বিশ্লেষণ করি:

১. কেন এটি $O(n^3)$?

লুপগুলোর গঠন লক্ষ্য করুন:

• বাইরের লুপ ($i$): $0$ থেকে $n-1$ পর্যন্ত চলে।
• মাঝখানের লুপ ($j$): এটিও $0$ থেকে $n-1$ পর্যন্ত চলে।
• ভেতরের লুপ ($k$): এটি তখনই break করে যখন $k \ge n - (i + j)$ হয়।

এখানে break স্টেটমেন্টটি মূলত একটি ত্রিভুজাকার বা পিরামিডাল (Pyramidal) কাজের ক্ষেত্র তৈরি করছে। যখন $i$ এবং $j$ ছোট হয়, তখন $k$ লুপটি অনেকবার চলে। যখন $i$ এবং $j$ বড় হয়, তখন $k$ লুপটি দ্রুত break করে।

২. গাণিতিক হিসাব

এই কোডটি মোট কতবার count++ করবে, তা বের করার জন্য আমাদের নিচের সমষ্টিটি (Summation) সমাধান করতে হবে:

এই গাণিতিক হিসাবটি সম্পন্ন করলে আমরা একটি ফলাফল পাই যা মূলত $\frac{n(n+1)(n+2)}{6}$ এর সমান।

এটি মূলত Tetrahedral Number এর সূত্র। আমরা যদি এই সমীকরণটি বিস্তৃত করি:

বিগ-ও ($O$) নোটেশনের নিয়মানুযায়ী, আমরা শুধুমাত্র সর্বোচ্চ ঘাতটি গ্রহণ করি এবং কনস্ট্যান্ট (যেমন $1/6$) বাদ দিই। ফলে চূড়ান্ত ফলাফল দাঁড়ায় $O(n^3)$।

৩. বাস্তব উদাহরণ

যদি $n = 100$ হয়:

• $n^3$ পদ্ধতিতে কাজ হতো $1,000,000$ বার।
• আপনার এই কোডটিতে কাজ হবে প্রায় $171,700$ বার।

যদিও break এর কারণে অপারেশন সংখ্যা প্রায় ৬ গুণ কমে গেছে, কিন্তু অ্যালগরিদমিক গ্রোথ রেট বা ইনপুট বাড়ার সাথে সাথে সময় বাড়ার হার এখনো $n^3$ অনুযায়ীই পরিবর্তিত হচ্ছে।

void f(int n, int depth) {
    if (depth == 0) return;
    for (int i = 0; i < n; i++) {
        print(i);
    }
    f(n, depth - 1);
    f(n, depth - 1);
}
// Called as: f(n, log2(n))

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n^2)$।

• লেভেল ০: $n$
• লেভেল ১: $2n$
• লেভেল ২: $4n$
• শেষ লেভেলে ($\log n$): $2^{\log n} \times n = n \times n = n^2$

for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j += i) {
        for (int k = j; k <= n; k += j) {
            ans++;
        }
    }
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n \log^2 n)$।

১. লুপগুলোর গাণিতিক বিশ্লেষণ

এই কোডটিতে তিনটি নেস্টেড লুপ রয়েছে যাদের কাজের ধরণ নিচে দেওয়া হলো:

• সবচেয়ে বাইরের লুপ ($i$): এটি $1$ থেকে $n$ পর্যন্ত চলে।
• মাঝখানের লুপ ($j$): এটি $i$-এর গুণিতক হারে বাড়ে ($j = i, 2i, 3i, \dots$). প্রতিটি $i$-এর জন্য এই লুপটি চলে প্রায় $n/i$ বার।
• সবচেয়ে ভেতরের লুপ ($k$): এটি $j$-এর গুণিতক হারে বাড়ে ($k = j, 2j, 3j, \dots$). প্রতিটি $j$-এর জন্য এই লুপটি চলে প্রায় $n/j$ বার।

২. গাণিতিক হিসাব (Harmonic Series)

পুরো কাজের পরিমাণ বের করতে আমাদের নিচের সামেশনটি সমাধান করতে হবে: \(\sum_{i=1}^{n} \sum_{j=i, 2i, \dots}^{n} \frac{n}{j}\)

আমরা জানি যে, একটি নির্দিষ্ট $i$-এর জন্য $j$-এর মানগুলো হলো $i \times m$ (যেখানে $m = 1, 2, \dots, n/i$). তাহলে ভেতরের লুপ দুটির সম্মিলিত কাজ:

\(\sum_{j \in \{i, 2i, \dots\}} \frac{n}{j} = \frac{n}{i} + \frac{n}{2i} + \frac{n}{3i} + \dots = \frac{n}{i} (1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n/i})\)হারমোনিক সিরিজের ধর্ম অনুযায়ী, $(1 + \frac{1}{2} + \dots + \frac{1}{x}) \approx \ln(x)$।সুতরাং, নির্দিষ্ট $i$-এর জন্য কাজ হচ্ছে: $\frac{n}{i} \log(\frac{n}{i})$।এখন সব $i$-এর জন্য মোট কাজ:\(\sum_{i=1}^{n} \frac{n}{i} \log(\frac{n}{i}) \leq \sum_{i=1}^{n} \frac{n}{i} \log(n) = n \log(n) \sum_{i=1}^{n} \frac{1}{i}\)যেহেতু $\sum \frac{1}{i}$ আবারও একটি হারমোনিক সিরিজ যা $\log n$ এর সমান, তাই চূড়ান্ত ফলাফল দাঁড়ায়:\(n \log n \times \log n = O(n \log^2 n)\)

সহজভাবে মনে রাখার কৌশল:

যখনই আপনি দেখবেন কোনো লুপ j += i বা k += j স্টাইলে চলছে (অর্থাৎ আগের লুপের ভেরিয়েবল দিয়ে লাফ দিচ্ছে), সেখানে Harmonic Series বা $\log n$ এর প্রভাব তৈরি হয়। এখানে দুটি এমন লুপ থাকায় আমরা $n \times \log n \times \log n$ পাচ্ছি।

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        int temp = j;
        while (temp > 0) {
            temp = temp & (temp - 1);
            count++;
        }
    }
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n^2 \log n)$।

১. লুপগুলোর বিশ্লেষণ

• বাইরের দুটি লুপ ($i$ এবং $j$): এই দুটি লুপ খুব সাধারণ লিনিয়ার লুপ। প্রতিটি লুপ $n$ বার ঘোরে। সুতরাং এই দুটি লুপের সম্মিলিত কমপ্লেক্সিটি হলো $n \times n = \mathbf{O(n^2)}$।

• ভেতরের $while$ লুপ: এই অংশটিই সবচেয়ে ইন্টারেস্টিং। এখানে temp = temp & (temp - 1) অপারেশনটি ব্যবহার করা হয়েছে।

২. বিট ম্যানিপুলেশন ট্রিক: Brian Kernighan’s Algorithm

temp & (temp - 1) অপারেশনটি একটি সংখ্যার বাইনারি রিপ্রেজেন্টেশন থেকে সবথেকে ডানদিকের সেট বিট (set bit বা $1$) টিকে সরিয়ে দেয়।

সহজ কথায়, এই লুপটি ততবার চলবে যতগুলো $1$ বা Set Bits সংখ্যাটির বাইনারি রূপে আছে।

• ধরা যাক $j = 7$ (বাইনারি 111), এখানে লুপটি ৩ বার চলবে।

• ধরা যাক $j = 8$ (বাইনারি 1000), এখানে লুপটি ১ বার চলবে।

৩. গাণিতিক হিসাব

একটি সংখ্যা $n$ এর সর্বোচ্চ কতগুলো সেট বিট থাকতে পারে? উত্তর হলো $\mathbf{\log_2 n}$।অর্থাৎ, প্রতিটি $j$-এর জন্য এই while লুপটি গড়ে $\log n$ এর বেশি চলতে পারে না।

তাহলে মোট কমপ্লেক্সিটি দাঁড়ায়:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        int x = n;
        while (x > 1) {
            x = x / 3;
        }
        sum++;
    }
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n^2 \log_3 n)$।

১. লুপগুলোর বিশ্লেষণ

• সবচেয়ে বাইরের লুপ ($i$): এটি $0$ থেকে $n-1$ পর্যন্ত চলে, অর্থাৎ এটি মোট $n$ বার ঘোরে।

• মাঝখানের লুপ ($j$): এটিও $0$ থেকে $n-1$ পর্যন্ত চলে, অর্থাৎ এটিও মোট $n$ বার ঘোরে।

• সবচেয়ে ভেতরের লুপ ($while$): এই লুপটি প্রতিবার $x = n$ থেকে শুরু হয় এবং প্রতি ধাপে $x$-কে $3$ দিয়ে ভাগ করে।

আমরা জানি, কোনো সংখ্যাকে যদি প্রতি ধাপে একটি নির্দিষ্ট ধ্রুবক (এখানে $3$) দিয়ে ভাগ করা হয় যতক্ষণ না সেটি $1$-এ পৌঁছায়, তবে সেই লুপটি মোট $\log_{\text{base}} (\text{value})$ বার চলে। এখানে বেস হলো $3$ এবং ভ্যালু হলো $n$, তাই এই লুপটি চলে $\log_3 n$ বার।

for (int i = 0; i < n; i++) {
    for(int j=1; j<i*i*i; j++){
        sum++;
    }
}

এই কোডটির টাইম কমপ্লেক্সিটি হলো $O(n^4)$।

১. লুপ দুটির বিশ্লেষণ

• বাইরের লুপ ($i$): এটি $1$ থেকে $n$ পর্যন্ত চলে।
• ভেতরের লুপ ($j$): এটি প্রতিটি $i$-এর জন্য $1$ থেকে $i^3$ (কিউব) পর্যন্ত চলে।

$O(2^n)$ বা Exponential Time

int fibonacci(int n) {
    if (n <= 1) return n;
    // প্রতিবার একটি ফাংশন আরও ২টি ফাংশনকে কল করছে
    return fibonacci(n - 1) + fibonacci(n - 2);
}

এখানে কেন কাজ (Operations) দ্বিগুণ হচ্ছে? যখন আপনি fibonacci(5) কল করেন:

• সেটি fibonacci(4) এবং fibonacci(3) কে কল করে (২টি কাজ)।
• ঐ ২টি আবার ৪টি নতুন কল তৈরি করে।
• ঐ ৪টি আবার ৮টি নতুন কল তৈরি করে।

সহজ কথা: যেখানে একটি সমস্যার সমাধান করতে গিয়ে আপনাকে বারবার একই কাজ “শাখা-প্রশাখা” আকারে করতে হয়, সেখানেই $O(2^n)$ তৈরি হয়। ___

Space Complexity

• Total Space: একটা প্রোগ্রাম চালাতে মোট যতটুকু মেমোরি লাগে (ইনপুট + এক্সট্রা কাজ)।
• Auxiliary Space: ইনপুট বাদে শুধু অ্যালগরিদমটা চালানোর জন্য বাড়তি যে মেমোরিটুকু তুমি খরচ করছো।

উদাহরণ ১: $O(1)$ Auxiliary Space (দক্ষ পদ্ধতি)

এখানে আমরা ইনপুট অ্যারের বাইরে শুধু একটি ভেরিয়েবল sum নিচ্ছি।

int solve(int arr[], int n) {
    int sum = 0; // এটা Auxiliary Space
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    return sum;
}

• Input Space: $O(n)$ (কারণ arr এ n সংখ্যক উপাদান আছে)।
• Auxiliary Space: $O(1)$ (কারণ আমরা শুধু একটি বাড়তি ভেরিয়েবল sum নিয়েছি, যা ইনপুটের সাইজের ওপর নির্ভর করে বাড়ছে না)।
• Total Space: $O(n) + O(1) \approx O(n)$।

উদাহরণ ২: $O(n)$ Auxiliary Space (কম দক্ষ পদ্ধতি)

ধরো, যোগ করার আগে আমরা সব সংখ্যা কপি করে অন্য একটা অ্যারেতে রাখছি।

int solve(int arr[], int n) {
    int tempArr[n]; // এটা Auxiliary Space
    for (int i = 0; i < n; i++) {
        tempArr[i] = arr[i]; // কপি করছি
    }
    // এরপর যোগ করছি...
}

• Input Space: $O(n)$।
• Auxiliary Space: $O(n)$ (কারণ আমরা ইনপুটের সমান সাইজের একটা নতুন অ্যারে tempArr তৈরি করেছি)।
• Total Space: $O(n) + O(n) = O(2n) \approx O(n)$।

১. $O(1)$ Space (কনস্ট্যান্ট স্পেস)

এখানে ইনপুটের সাইজ যাই হোক, আমরা মাত্র ১-২টা ভেরিয়েবল ব্যবহার করছি। মেমোরি একদম ফিক্সড।

// findMax: এখানে শুধু 'maxVal' আর 'i' ভেরিয়েবল আছে
int findMax(int arr[], int n) {
    int maxVal = arr[0]; // ১টি ভেরিয়েবল
    for (int i = 1; i < n; i++) { // লুপের জন্য ১টি ভেরিয়েবল
        if (arr[i] > maxVal) maxVal = arr[i];
    }
    return maxVal;
}

• কেন $O(1)$? কারণ n যদি ১০ লাখও হয়, তোমার এক্সট্রা ভেরিয়েবল কিন্তু ওই ২টাই থাকছে।