Big_O_Notation Explained in Bangla

Big O Notation

Big-O notation হচ্ছে আমাদের কোনো একটা function এর ইনপুট বাড়ার সাথে সাথে কতটা টাইম কমপ্লেক্সিটি ও কতটা স্পেস কমপ্লেক্সিটি হচ্ছে সেটা নির্ণয় করা। এটি একটি টুল যার সাহায্যে কোনো একটা অ্যালগরিদমের রানটাইমের উপর ভিত্তি করে টাইম কমপ্লেক্সিটি বের করা যায়।
Big O notation কোনো অ্যালগরিদমের টাইম কমপ্লেক্সিটি ও কতটা স্পেস কমপ্লেক্সিটি নির্ণয় করতে ব্যবহৃত হয়, তাদের মধ্যে বৃদ্ধির হার হিসেবে প্রকাশিত হয়। উদাহরণস্বরূপ,
O(1), O(log n), O(n), O(n log n), O(n^2) ইত্যাদি।

Big-O notation এর মাধ্যমে আমাদের প্রতিনিয়ত ব্যবহৃত কয়েকটা জাভাস্কিপ্ট মেথত এর টাইম কমপ্লেসিটি ও স্পেস কমপ্লেসিটি নির্ণয় করি

=> Big O(n) - যখন কোনো ইনপুট আমাদের অনিশ্চিত থাকে ( মানে কতগুলো ইনপুট অথবা ভেলু থাকতে পারে অথবা আউটপুট আসতে পারে আমরা জানি না ) তখন আমরা সেটাকে n হিসেবে নেই, এবং যে সকল মেথডের টাইম কমপ্লেক্সিটি আমরা নির্ণয় করার সময় এইরকম ভাবে অনিশ্চিত ইনপুট আসতে পারে পাই সেগুলোকে আমরা Big O(n) বলি।

=> Big O(1) -

যখন কোনো ইনপুট আমাদের নিশ্চিত থাকে
( মানে আমরা জানি যে ওইটা শুধুমাত্র একটা আউটপুট দিবে আমাদের কন্ডিশন অনুযায়ী ) তখন আমরা সেটাকে 1 ধরি, এবং যে সকল মেথডের টাইম কমপ্লেক্সিটি আমরা নির্ণয় করার সময় এইরকম ভাবে নিশ্চিত ইনপুট আসতে পারে পাই সেগুলোকে আমরা Big O(1) বলি।

Object

• Object.keys - Big O(n)

  ( এটায় Big O(n) কারণ একটি object এ অনেক keys তাকতে পারে এটা বলা মুশকিল যে ওই object এর মধ্যে মোট কতটি entries তাকবে, তাই আমরা ধরে নিলাম যে একটা n ইনপুটে থাকবে এবং সেই n এ যত ইচ্ছা দেওয়া হবে তাই এটা n এর উপর ডিপেন্ডেড এবং এর জন্যই এটা Big O(n) )

• Object.entries - Big O(n)

  ( same as object.keys )

• Object.values - Big O(n)

  ( same as object.keys )

• Object.hasOwnProperty - Big O(1)

  ( এটায় Big O(1) কারণ আমরা যখন কোনো property সার্চ করবো তখন তো আমরা একটা value ই পাবো এবং এর জন্যই এটা Big O(1) )

Array

• push, pop - Big O(1)

  ( এটায় Big O(1) কারণ একটি array তে আমরা যখন push or pop এর মাধ্যমে কোনো element যুক্ত করি তখন সেই element টি ওই array এর শেষের দিকে যুক্ত হয় অথবা ডিলিট হয়, যার জন্য কোনো element এর ইনডেক্স পরিবর্তন করতে হয় না এবং এর জন্যই এটা Big O(1) )

• shift, unshift - Big O(n)

  ( এটায় Big O(n) কারণ একটি array তে আমরা যখন shift or unshift এর মাধ্যমে কোনো element যুক্ত করি তখন সেই element টি ওই array এর শুরুর দিকে যুক্ত হয় অথবা ডিলিট হয়, যার জন্য আগের element দের ইনডেক্স পরিবর্তন করতে হয়। তাই এখানে n বার নতুন element যুক্ত হতে পারে যার জন্যই এটা Big O(n) )

• search - Big O(n)

  ( এটায় Big O(n) কারণ একটি array তে কতগুলো value তাকবে তা বলা যাবে না এবং আমরা যদি ওই array তে কোনো কিছু search করি তাহলে আমাদের ওই array তে থাকা প্রতিটি element এর মধ্যে দিয়ে খুজতে হবে আমাদের কাংকিত element টিকে এবং সেটা n তম বার ও হতে পারে যার জন্যই এটা Big O(n) )

• access - Big O(1)

  ( এটায় Big O(1) কারণ একটি array থেকে আমরা যখন কোনো একটা element access করতে চাই তার index এর মাধ্যমে তখন কিন্তু আমরা সরাসরি ওই element টাকে access করতে পারি এবং সেটা একটি element হয় যার জন্যই এটা Big O(1) )

• forEach - Big O(n)

  ( এটায় Big O(n) কারণ একটি forEach এ কতগুলো ইনপুট আসবে সেটা আমরা জানি না। এখন সেটা অনেক বড় কোনো ইনপুট হতে পারে আবার ছোটও হতে পারে তার জন্যই এটা Big O(n) )

• map - Big O(n)

  ( এটায় Big O(n) কারণ একটি map এ কতগুলো ইনপুট আসবে সেটা আমরা জানি না। এখন সেটা অনেক বড় কোনো ইনপুট হতে পারে আবার ছোটও হতে পারে তার জন্যই এটা Big O(n) )

• filter - Big O(n)

  ( এটায় Big O(n) কারণ একটি filter এ কতগুলো ইনপুট আসবে সেটা আমরা জানি না। এখন সেটা অনেক বড় কোনো ইনপুট হতে পারে আবার ছোটও হতে পারে তার জন্যই এটা Big O(n) )

• reduce - Big O(n)

  ( এটায় Big O(n) কারণ একটি reduce এ কতগুলো ইনপুট আসবে সেটা আমরা জানি না। এখন সেটা অনেক বড় কোনো ইনপুট হতে পারে আবার ছোটও হতে পারে তার জন্যই এটা Big O(n) )