মডিউল ১: টাইম এন্ড স্পেস কমপ্লেক্সিটি

Introduction

আজকে আমরা যা যা শিখবো

1. টাইম কমপ্লেক্সিটি সম্পর্কে ভালো ধারনা পাবো
2. কোড দেখে টাইম কমপ্লেক্সিটি নির্ণয় করতে পারবো
3. একটি কোড কতটা ইফিশিয়েন্ট তা যাচাই করতে পারবো
4. প্রবলেম এ দেয়া ইনপুট দেখে কোন কমপ্লেক্সিটি এর সলিউশন লিখতে হবে তা নিয়ে ধারনা পাবো
5. স্পেস কমপ্লেক্সিটি নিয়ে ধারনা পাবো

Time Complexity

টাইম কমপ্লেক্সিটি শুনে আমাদের প্রথমে মনে হতে পারে, আমাদের কোড রান হতে কত সময় নেয় তার একটি ম্যাজারমেন্ট। ব্যাপারটি আসলে তা না। একটি কোড রান হতে কত সময় লাগছে তা আমরা কখনো হিসাব করি না। কারন সেইম কোড উইন্ডোজে রান করতে যত সময় লাগছে ম্যাক এ রান হতে তত সময় নাও লাগতে পারে। আবার 32-bit উইন্ডোজে যত সময় লাগছে 64-bit উইন্ডোজে হয়তো তার থেকে কম লাগতে পারে। এখন তাহলে আমরা কিভাবে পরিমাপ করব কোন কোডটি ফাস্ট এবং কোন কোডটি স্লো। এই পরিমাপটিই হচ্ছে টাইম কমপ্লেক্সিটি। টাইম কমপ্লেক্সিটিতে আমরা ইনপুট এর প্রেক্ষিতে অপারেশন নাম্বার কিরকম হতে পারে তা ম্যাজার করি।

আমাদের কোডটি যদি হয় এরকমঃ

for(int i=0;i<n;i++)

 {

 cout << "Hello" << endl;

}

এক্ষেত্রে ইনপুট n এর মান যদি ১০ হয় তাহলে কোডটি ১০বার হ্যালো প্রিন্ট করবে। অর্থাৎ ১০ বার প্রিন্ট অপারেশন চালাবে। তেমনি ইনপুট n এর মান যদি ১০০০০০০ (১০ লক্ষ বার) হয় তাহলে কোডটি ১০ লক্ষ বার হ্যালো প্রিন্ট করবে। এইযে ইনপুট এর মানের সাথে কোডের অপারেশনের একটি সম্পর্ক এটিই পরিমাপ করা হয় টাইম কমপ্লেক্সিটিতে।

Asymptotic Notation: টাইম কমপ্লেক্সিটির একক বলা যায় Asymptotic Notation কে। মূলত ৩ ধরনের Asymptotic Notation রয়েছে।​ ​

• Big O Notation - Worst case​ ​
• Theta Notation - Average case​ ​
• Omega Notation - Best case

মনে করি আমার কাছে ১০০টি সংখ্যা রয়েছে। সেখান থেকে আমি একটি নির্দিষ্ট সংখ্যাকে খুজছি। তাহলে অবশ্যই আমাকে প্রথম থেকে এক এক করে সবগুলো সংখ্যা খুজে দেখতে হবে। এখন আমি যদি প্রথম বার খুজতে যেয়েই আমার কাংখিত সংখ্যাটি পেয়ে যাই তাহলে সেটিকে বেস্ট কেস বলা যায়। আমি যদি ৫০বার খুজার পর আমার সংখ্যাটি পাই তাহলে এভারেজ কেস বলতে পারি। এবং আমি যদি সবগুলো সংখ্যা খুজা শেষে (১০০ বার) একদম লাস্টে যেয়ে আমার সংখ্যাটি পাই তাহলে সেটিকে worst কেস বলা যেতে পারে।

টাইম কমপ্লেক্সিটি ক্যালকুলেট করার সময় আমরা সবসময় worst কেসটা নেই।

টাইম কমপ্লেক্সিটি কেন প্রয়োজনঃ

মনে করি, আমরা দুজন স্টুডেন্টকে একটি প্রবলেম দিলাম। প্রবলেমটি হলো ১ থেকে n পর্যন্ত যোগ করতে হবে। এখন একজন স্টুডেন্ট n ইনপুট নেওয়ার পর ১ থেকে n পর্যন্ত লুপ চালিয়ে যোগফল বের করল। আরেকজন স্টুডেন্ট n*(n+1)/2 ( ১ থেকে n পর্যন্ত স্বাভাবিক সংখ্যার যোগফল এর সূত্র) দিয়ে করে ফেলল। এখন আমাদের যদি বের করতে হয় কার কোডটি বেটার, তাহলে আমাদের দুজনের কোডের কমপ্লেক্সিটি বের করতে হবে। এক্ষেত্রে দুজনের কোডই কারেক্ট আন্সার দিবে কিন্তু প্রথম স্টুডেন্ট এর কোড n পর্যন্ত লুপ চালিয়ে যোগ করবে। n এর মান যদি হয় ১০,০০০ তাহলে প্রথম স্টুডেন্ট এর কোড ১০,০০০টি অপারেশন চালাবে। অপরদিকে দ্বিতীয় স্টুডেন্ট, যে সূত্র দিয়ে করেছে তার কোড মাত্র ১টি অপারেশন চালাবে। অবশ্যই দ্বিতীয় স্টুডেন্ট এর কোড বেটার। এটি আমরা বলতে পারলাম টাইম কমপ্লেক্সিটির সাহায্যে।

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

O(N) টাইম কমপ্লেক্সিটিকে বলা হয় লিনিয়ার টাইম কমপ্লেক্সিটি । ইনপুটের সাপেক্ষে আমাদের​ ​ প্রোগ্রামের অপারেশন যদি সমান ভাবে বাড়তে থাকে তবে সেই কমপ্লেক্সিটি কে আমরা বলতেছি লিনিয়ার টাইম কমপ্লেক্সিটি বা O(N) টাইম কমপ্লেক্সিটি। আরেকটু ক্লিয়ার করে বললে , আমার প্রোগ্রামে যদি এমন কোনো ইন্সট্রাকশন থাকে যা একটি ভ্যরিয়েবল ইনপুট N এর উপর নির্ভর করে অর্থাৎ N​ ​ এর ভ্যালু ১০ হলে কাজটি ১০ বার সম্পাদন হয় , N এর ভ্যালু ১০০ হলে কাজটি ১০০ বার সম্পাদন হয় , N এর ভ্যালু ১০০০ হলে কাজটি​ ​ ১০০০ বার সম্পাদন হয় সেই ক্ষেত্রে আমরা বলতে পারি , আমাদের কোডটির টাইম কমপ্লেক্সিটি O(N).

চলুন ,কিছু কোডের উদাহরণ দেখে বিষয়টি আরো ভালোভাবে বুঝার চেষ্টা করি ।

Problem 1 :

int n ; cin >> n ;


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

cout << i << endl;

}

Input : 10

Output : 0 1 2 3 4 5 6 7 8 9

উপরোক্ত কোডে নিচের for লুপটি ঠিক কতবার চলবে আমরা তা প্রোগ্রাম এ ইনপুট দেয়ার আগে বলে দিতে পারবো না। এখানে লুপটি কতবার চলবে , এবং এর মধ্যে দেয়া প্রিন্ট ইন্সট্রাকশন টি কতবার সম্পাদন হবে তা সম্পূর্ণ নির্ভর করছে একটি ভ্যারিয়েবল N এর উপর। N এর সুতারাং এই কোডের টাইম কমপ্লেক্সিটি হবে O(N) .

Problem 2 :

int n ; cin >> n ;


for(int i =0;i<n ;i+=2){

cout << i << " ";

}

Input : 10

Output : 0 2 4 6 8 10

এই প্রবলেমের জন্য যদি আমরা N এর ভ্যালু ১০ ধরে নিই , তবে প্রথমে লুপটি তে i এর মান শুরু হবে ০ হতে। এরপরের স্টেপ এ i এর মান হয়ে যাবে 2 ,এরপর 4 , এরপর 6 , এরপর 8 এবং এর পরের স্টেপ এ i এর মান ১০ হয়ে যাবে এবং কন্ডিশন মিথ্যা হয়ে যাওয়ার কারণে লুপ টি ব্রেক করবে। আমরা যদি একটু খেয়াল করে দেখি সর্বমোট ৫ বার লুপের ভিতরের কাজটি সম্পাদন হয়েছে , যা আসলে ১০ এর অর্ধেক। যদি N এর ভ্যালু হতো ১০০ তবে কাজটি সম্পাদন হতো ১০০ এর অর্ধেক অর্থাৎ ৫০ বার । তার মানে আমরা বলতে পারি এই কোডের টাইম কমপ্লেক্সিটি হবে O(N/2). কিন্তু আমরা পূর্বের মডিউলে দেখে এসেছি , টাইম কমপ্লেক্সিটি নির্ণয়ের সময় আমরা সর্বদা ধ্রুব যে অংশটুকু আছে তা বাদ দিয়ে দিবো। সুতারাং এই কোডের টাইম কমপ্লেক্সিটি হবে O(N).​ ​

Problem 3 (Reversing an Array) :

for(int i =0;i<n/2 ;i++){

int temp = a[i] ;

a[i] = a[n-i-1] ;

a[n-i-1] = a[i] ;

}

উপরের কোড দ্বারা আমরা একটি N সাইজের এরে কে রিভার্স করতে পারি । এখানে যদি খেয়াল করে দেখি , এরে এর সাইজ যত হবে লুপটি তার অর্ধেক পরিমান চলবে । এবং সাথে সাথে এরেটি রিভার্স হয়ে যাবে। যেহেতু N এর অর্ধেক পরিমান ইন্সট্রাকশন এখানে সম্পাদন হচ্ছে , তাই Problem 2 এর মতো এই কোডের ও টাইম কমপ্লেক্সিটি হবে O(N).

Problem 4 :

// loop 1 :

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

cout << i << " ";

}

cout << endl;


//loop 2 :

for(int j =1;j<=M ;j++){

cout << j << " ";

}

Input : 10 5

Output : 1 2 3 4 5 6 7 8 9 10

1 2 3 4 5

উপরের কোডে প্রথম লুপটি মোট N বার চলবে এবং তা শেষ হলে দ্বিতীয় লুপটি মোট M বার চলবে । ধরি , N এর মান ১০ , এখন উপরের লুপটি ১০ বার চলবে, এরপর ধরি , M এর মান ৫ , এখন দুই নাম্বার লুপটি ৫ বার চলবে । সুতারাং পুরো প্রোগ্রাম এ সর্বমোট ১০+৫ = ১৫ টি কাজ সম্পাদন হচ্ছে। এখানে লক্ষ্য করে দেখা যায় , যদি আমরা পুরা কোড বিবেচনা করি তবে সর্বমোট আসলে কতটি কাজ সম্পাদন হচ্ছে তা হচ্ছে N এবং M এর যোগফলের সমান। সুতারাং এই কোডের টাইম কমপ্লেক্সিটি হলো O(N+M).

সহজে মনে রাখার উপায়ঃ

আমার প্রোগ্রামে যদি এমন কোনো ইন্সট্রাকশন থাকে যা একটি ভ্যরিয়েবল ইনপুট N এর উপর নির্ভর করে অর্থাৎ N এর ভ্যালু ১০ হলে কাজটি ১০ বার সম্পাদন হয় , N এর ভ্যালু ১০০ হলে কাজটি ১০০ বার সম্পাদন হয় , N এর ভ্যালু ১০০০ হলে কাজটি ১০০০ বার সম্পাদন হয় সেই ক্ষেত্রে আমরা বলতে পারি , আমাদের কোডটির টাইম কমপ্লেক্সিটি O(N).

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

O(logN) টাইম কমপ্লেক্সিটিকে বলা হয় লগারিদমিক টাইম কমপ্লেক্সিটি । ইনপুটের বৃদ্ধির সাপেক্ষে আমাদের প্রোগ্রামের অপারেশন যদি​ ​ একটি​ ​ নির্দিষ্ট বেস এর লগারিদমিক​ ​ হারে কমতে থাকে সেই কমপ্লেক্সিটি কে আমরা বলতেছি লগারিদমিক টাইম কমপ্লেক্সিটি বা O(lognN) টাইম কমপ্লেক্সিটি। যেমন ধরুন , আমাদের প্রোগ্রামে যদি এমন কোনো ইন্সট্রাকশন থাকে যা একটি ভ্যরিয়েবল ইনপুট N এর লগারিদমিক মান এর উপর নির্ভর করে অর্থাৎ N​ ​ এর ভ্যালু ১০ হলে কাজটি কম বেশি​ ​ log10 ~ ৩​ ​ বার সম্পাদন হয় , N এর ভ্যালু ১০০ হলে কাজটি​ ​ কম বেশি​ ​ log100 ~ 6 বার সম্পাদন হয় , N এর ভ্যালু ১০০০ হলে কাজটি​ ​ কম বেশি​ ​ log1000 ~ 9 বার সম্পাদন হয় সেই ক্ষেত্রে আমরা বলতে পারি , আমাদের কোডটির টাইম কমপ্লেক্সিটি O(logN). খেয়াল করে দেখবেন , এইক্ষেত্রে আমাদের কোডের টাইম কমপ্লেক্সিটি আগের মডিউলের টাইম কমপ্লেক্সিটি O(N) এর মতো ইনপুটের সাথে সাথে সমান হারে বাড়ছে না।​ ​

চলুন ,কিছু কোডের উদাহরণ দেখে বিষয়টি আরো ভালোভাবে বুঝার চেষ্টা করি ।

Problem 1 :

 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

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

Problem 2 :

 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 থেকে শুরু হবে , 12 = 2 (১ বার) -> 22-> 4 (২ বার) -> 42 -> 8 (৩ বার) , 82 = 16> 10 , লুপটি এখানে থেমে যাবে। সুতারাং সর্বমোট log10 ~3 বার এই লুপটি চলেছে । এরপর আসেন , N এর মান ১০০ এর জন্য টেস্ট করে দেখি বিষয় টি। i =1 , থেকে শুরু হবে এরপর 12 = 2 (১ বার) -> 22-> 4 (২ বার) -> 42 -> 8 (৩ বার) , 82 = 16 (4 বার) -> 162 -> 32 (৫ বার) -> 322 = 64 (৬ বার) -> 64*2=128>100 এখানে লুপটি থেমে যাবে। সুতারাং সর্বমোট log100 ~6 বার লুপটি চলেছে। সবশেষে এখান থেকে আমরা বুঝতে পারতেছি যে কোন একটি সংখ্যা কে ম্যাক্সিমাম কয়বার ২ দিয়ে গুণ করা যাবে যাতে করে তা N এর থেকে ছোট হয় / সমান হয় , তা হলো ঐ সংখ্যার লগের সমান অর্থাৎ logN এর সমান । তাই উপরের কোডের টাইম কমপ্লেক্সিটি হচ্ছে O(logN).

Problem 3 :

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)

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

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

Problem 1 :

 int n ; cin >> n ;


for(int i =1 ;i<=sqrt(n) ;i++){

 if(n%i==0){

 cout << i << " ";

 cout << n/i << " ";

 }

}

Input : 100

Output : 100 50 25 12 6 3

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

Problem 2 :

 int i = 1 , s = 1 ;


while(s<n){

 s = s + i ;

 i++ ;

}

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

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

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

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

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

সহজে মনে রাখার উপায়ঃ

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

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

উদাহরন ১ঃ

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)

টাইম কমপ্লেক্সিটি থেকে টাইম ক্যালকুলেট করা

আমরা নরমালি যখন কোন অনলাইন জাজে প্রবলেম সল্ভ করতে যাই, তখন সেই প্রবলেমে একটি টাইম লিমিট থাকে। বেশিরভাগ ক্ষেত্রেই এই টাইম লিমিটটি ১ থেকে ৩ সেকেন্ডের মধ্যে হয়ে থাকে। আমাদের কম্পিউটার নরমালি ১ সেকেন্ডে 10^7 অপারেশন কমপ্লিট করতে পারে।

তাহলেঃ

10^7 অপারেশন কমপ্লিট করতে সময় লাগছে 1 সেকেন্ড।

10^8 অপারেশন কমপ্লিট করতে সময় লাগছে 10 সেকেন্ড।

10^9 অপারেশন কমপ্লিট করতে সময় লাগছে 100 সেকেন্ড।

তাহলে ১ থেকে ৩ সেকেন্ডে আমরা 10^7 থেকে 3*10^7 পর্যন্ত অপারেশন চালাতে পারব। তাহলে আমাদের যেকোন প্রবলেমের এমন সলুশন বের করতে হবে যেন তা মোটামোটি 10^7 অপারেশনের মধ্যে কমপ্লিট হয়।

আমরা মনে রাখার জন্য এটি ফলো করতে পারিঃ

Time Complexity	Maximum N (Approximate)
O(1)	10^18
O(logN)	10^18
O(sqrt(N))	10^14
O(N)	10^7
O(N logN)	10^5
O(N²)	10^3
O(N³)	10^2
O(2^N)	20
O(N!)	10

Space Complexity

আমরা টাইম কমপ্লেক্সিটি দেখেছি। ঠিক তেমনি মাঝে মাঝে আমাদের স্পেস কমপ্লেক্সিটিও বের করার প্রয়োজন হয়। আমাদের কোড মেমরিতে কিরকম স্পেস কনজিউম করছে তা বের করার প্রয়োজন পরতে পারে। অথবা দুটি কোড এর মধ্যে কোন কোডটি মেমরিতে বেশি জায়গা নিবে তা বের করার জন্য দুটি কোডের স্পেস কমপ্লেক্সিটি বের করতে হবে। আমরা কয়েকটি উদাহরন এর মধ্যে স্পেস কমপ্লেক্সিটি বুঝে নেওয়ার ট্রাই করি।

উদাহরন-১ঃ

int result = 0; // একটি ভেরিয়েবল নেওয়া হয়েছে।

for(int i=0;i<n;i++) // একটি লুপ চলছে ০ থেকে n পর্যন্ত, তাই এই কোডের টাইম কমপ্লেক্সিটি O(N)
{

 result+=i; // প্রতিবার যোগফল আগের ভেরিয়েবলেই রাখা হচ্ছে।

}

 // এখানে টাইম কমপ্লেক্সিটি O(N) কিন্তু স্পেস কমপ্লেক্সিটি O(1) কারন এখানে লুপ চলার কারনে নতুন কোন ভেরিয়েবল নেওয়া হচ্ছে না।

উদাহরন-২ঃ

int ar[n]; // একটি এরে নেওয়া হচ্ছে n সাইজের। তাই এর স্পেস কমপ্লেক্সিটি O(N)। কারন এখানে এরে সাইজ ডিপেন্ড করছে ইনপুট n এর মানের উপর। ইনপুট মান যত বেশি হবে এরেটি মেমরিতে তত বেশি জায়গা দখল করবে।

for(int i=0;i<n;i++)

{

 cout << a[i] << endl; // আর কোন ভেরিয়েবল নেওয়া হচ্ছে না।

}

 // তাই এই কোডের স্পেস কমপ্লেক্সিটি O(N)