Big-O সহজ ভাষায়: time ও space complexity

Big-O notation বর্ণনা করে input-এর আকার বাড়লে algorithm-এর চলার সময় (বা memory) কীভাবে বাড়ে। এটি মেশিনের গতি ও ছোট বিস্তারিত উপেক্ষা করে বৃদ্ধির আকৃতিতে মন দেয়। এটি coding interview-এর সাধারণ ভাষা এবং পদ্ধতি বাছাইয়ের খুব ব্যবহারিক টুল।

O(n) মানে কী?

Input-এ n টি item থাকলে এবং কাজ n-এর অনুপাতে বাড়লে algorithm O(n), "order n" বা "linear"। Input দ্বিগুণ করলে সময় মোটামুটি দ্বিগুণ।

Big-O বর্ণনা করে বড় input-এ বৃদ্ধির ঊর্ধ্বসীমা, সাধারণত সবচেয়ে খারাপ ক্ষেত্রে, এবং constant ও নিম্নক্রম পদ বাদ দেয়:

• 3n + 10 হয় O(n)।
• n² + 5n + 2 হয় O(n²)।

সাধারণ complexity, দ্রুততম থেকে ধীরতম

Big-O	নাম	উদাহরণ
O(1)	Constant	Index দিয়ে array element পড়া, hash map lookup (গড়ে)
O(log n)	Logarithmic	Binary search
O(n)	Linear	একবার তালিকা scan
O(n log n)	Linearithmic	দক্ষ sorting (merge sort, সাধারণ বিল্ট-ইন sort)
O(n²)	Quadratic	একই তালিকায় nested loop, সরল sort
O(2ⁿ)	Exponential	সরল recursive subset বা naive Fibonacci
O(n!)	Factorial	সব permutation তৈরি

বড় n-এ ফাঁক বিশাল। n = 1,000,000-এ O(n) প্রায় দশ লাখ ধাপ আর O(n²) এক ট্রিলিয়ন।

কোড কীভাবে বিশ্লেষণ করবেন

n টি item-এর ওপর একক loop O(n)।

for (const x of items) { total += x; }     // O(n)

Nested loop গুণ হয়।

for (const a of items) {
  for (const b of items) { compare(a, b); }   // O(n * n) = O(n²)
}

একটির পর একটি দুই loop যোগ হয়, এবং বড় পদটি রাখেন।

for (...) {...}   // O(n)
for (...) {...}   // O(n)
// মোট O(n + n) = O(n)

প্রতি ধাপে সমস্যা অর্ধেক করলে O(log n)।

while (lo <= hi) { mid = (lo + hi) >> 1; ... }   // binary search, O(log n)

ভিন্ন input-কে ভিন্ন অক্ষর দিন। A তালিকা (আকার a) ও B তালিকা (আকার b) loop করলে O(a + b), nested হলে O(a * b)। দুটিকেই n বলবেন না।

Recursion: কতবার কল হয় এবং প্রতিটিতে কাজ কত গুনুন। যে function প্রতি স্তরে নিজেকে দুবার ডাকে, গভীরতা n পর্যন্ত, তা প্রায় O(2ⁿ)। Memoization (ফল cache করা) এটি অনেক কমাতে পারে।

Space complexity

Space complexity মাপে input বাড়লে ব্যবহৃত বাড়তি memory।

• কয়েকটি variable: O(1)।
• সর্বোচ্চ n টি item রাখা নতুন array বা hash map: O(n)।
• Recursion stack জায়গা নেয়: গভীরতা d মানে O(d)।

প্রায়ই জায়গা দিয়ে সময় কেনা যায়। Hash set O(1) space-এ O(n²) সময়ের বদলে O(n) space-এ O(n) সময়ে ডুপ্লিকেট যাচাই করতে দেয়।

সেরা, গড় ও সবচেয়ে খারাপ ক্ষেত্র

• সবচেয়ে খারাপ ক্ষেত্র Big-O সাধারণত যা জানায়: সবচেয়ে ধীর পরিস্থিতি।
• গড় ক্ষেত্র সাধারণ আচরণ।
• Amortised খরচ মাঝে মাঝে ব্যয়বহুল ধাপ গড় করে। Resize কখনো O(n) খরচ হলেও dynamic array-তে যোগ করা O(1) amortised।

উদাহরণ: quicksort গড়ে O(n log n) কিন্তু সবচেয়ে খারাপ ক্ষেত্রে O(n²)।

সাধারণ ক্রিয়ার complexity

Structure	Access	খোঁজা	যোগ	মোছা
Array	O(1)	O(n)	O(n)	O(n)
Hash map / set (গড়ে)		O(1)	O(1)	O(1)
Linked list	O(n)	O(n)	জানা node-এ O(1)	জানা node-এ O(1)
Balanced search tree		O(log n)	O(log n)	O(log n)
Heap			O(log n)	শীর্ষে O(log n)

Interview-এ Big-O ব্যবহার

১. Brute-force সমাধান দিয়ে শুরু করুন এবং তার complexity বলুন। ২. অপচয় খুঁজুন: পুনরাবৃত্ত কাজ, অপ্রয়োজনীয় sorting, বারবার খোঁজা। ৩. ভালো data structure (hash map, set, heap) বা প্যাটার্ন (two pointers, sliding window, binary search) দিয়ে উন্নত করুন। ৪. চূড়ান্ত সমাধানের time ও space complexity জোরে বলুন এবং লাভ-ক্ষতি ব্যাখ্যা করুন। ৫. সীমা বিবেচনা করুন: n 100 পর্যন্ত হলে O(n²) চলতে পারে; 10⁶ হলে প্রায় O(n log n) বা ভালো লাগে।

মোটামুটি নিয়ম: সাধারণ মেশিন সেকেন্ডে ১০⁸ মাত্রার সরল ক্রিয়া করে, তাই n = 10⁵-এ O(n²) সমাধান খুব ধীর।

সাধারণ ভুল ধারণা

• Big-O সঠিক সময় নয়। ছোট input-এ দ্রুত O(n²) ধীর O(n)-কে হারাতে পারে।
• Big-O উপেক্ষা করলেও আসল সিস্টেমে constant গুরুত্বপূর্ণ।
• বিল্ট-ইন function-এর নিজস্ব খরচ আছে। Loop-এর ভেতরে list.includes(x)-এর মতো কল আরেকটি O(n) লুকায়।
• কিছু ভাষায় loop-এ string জোড়া O(n²) হতে পারে।

মূল কথা: Big-O দেখায় input-এর সাথে খরচ কীভাবে বাড়ে। সাধারণ শ্রেণিগুলো শিখুন, loop ও recursion গুনুন, space-ও মনে রাখুন, এবং সমাধান ব্যাখ্যায় সবসময় complexity বলুন।

---

Interview প্রস্তুতি ও DSA সিরিজ, পর্ব ১ (মূল প্যাটার্ন): 1 নম্বর (মোট 5)।