Complexity বলতে সাধারনত Time Complexity কে বোঝায়। যখন আমাদের কে জিজ্ঞাসা করা হয় কোনো প্রোগ্রামের Complexity কত তখন সাধারনত টাইম Complexity কেই বুঝতে হবে। আমাদের টাইম Complexity বোঝার আগে আরেকটি টার্ম Big O নোটেশন বোঝতে হবে। Big O নোটেশন হচ্ছে Complexity প্রকাশক। অর্থাৎ Big O হচ্ছে Complexity লিখে প্রকাশ করার নোটেশন।

# লিনিয়ার Complexity ঃ

কোনো প্রোগ্রামের মধ্যে যদি নিদিষ্ট সংখ্যক instruction থাকে অথবা কিছু নিদিষ্ট সংখ্যক operation থাকে তাহলে আমরা
বলতে পারব এই প্রোগ্রামের Complexity হচ্ছে লিনিয়ার।
এবং লিনিয়ার Complexity কে Big O নোটেশন দ্বারা প্রকাশ করলে তা সর্বদা হবেঃ O(1)
নিচের প্রোগ্রামটি দেখা যেতে পারেঃ

result = i*(i+1)/2

এখানে আমাদের প্রোগ্রামটির মধ্যে কয়েকটি নিদিষ্ট সংখ্যক operation রয়েছে।
যেমনঃ ১টি যোগ, ১টি গুন, ১টি ভাগ, এবং সর্বশেষে একটি অ্যাসাইনমেন্ট operation
এখানে n এর মান যদি 1 হয় তাহলেও এই নিদিষ্ট সংখ্যক operation হবে। আবার n এর মান যদি 1000 হয় তাহলেও এই একই সংখ্যক operation হবে। অর্থাৎ আমরা বলতে পারি এই প্রোগ্রামটি n এর মানের উপর নির্ভরশীল নয়। যেহেতু প্রোগ্রামটি n এর মানের উপর নির্ভরশীল নয় এবং সর্বদা একই নিদিষ্ট সংখ্যক instruction এর উপর কাজ করছে তাই এই প্রোগ্রামটির Complexity কে আমরা লিনিয়ার বলতে পাড়ি এবং আমরা জানি লিনিয়ার Complexity কে O(1) দিয়ে প্রকাশ করা হয়।

# Big-O(n) Complexity:

এখন নিচের কোডটি লক্ষ করিঃ

for(i=0; i<=n; i++){
     result = result + i
}

কোডটিতে দেখা যাচ্ছে, একটি লুপ আছে এবং এই লুপের মধ্যে ১টি যোগ, এবং ১টি অ্যাসাইনমেন্ট operation রয়েছে।
যদি n এর মান 1 হয় তাহলে আমাদের মোট instruction execute হবে: 1 x 2 = 2
যদি n এর মান 100 হয় তাহলে আমাদের মোট instruction execute হবে: 100 x 2 = 200
এবং যদি n এর মান 10000 হয় তাহলে আমাদের মোট instruction execute হবে: 10000 x 2 = 20000
দেখা যাচ্ছে যে n এর মানের উপর নির্ভর করে আমাদের প্রোগ্রামটির instruction সংখ্যা বাড়ছে। তাই বলতেই পাড়ি যে আমাদের এই প্রোগ্রামটি n এর মানের উপর নির্ভরশীল।
তাহলে আমাদের এই প্রোগ্রামটির Complexity হবেঃ O(2*n) => O(n)
এখানে 2 হচ্ছে constant, এবং কোনো প্রোগ্রামের constant কে আমরা বাদ দিয়ে দিতেই পাড়ি। কারন constant সংখ্যক instruction খুব দ্রুত সংগঠিত হয়ে যায় ফলে আমাদের প্রোগ্রামের execution টাইমে তেমন কোনো effect ফেলবে না।

# Big-O(n^2) Complexity:

নিচের প্রোগ্রামটি লক্ষ করিঃ

for(i=0; i<n; i++){
    for(j=0; j<n; j++){
       count = count + 1
    }
}

উপরের প্রোগ্রামটির মধ্যে ২টি লুপ চলছে, এদের মধ্যে একটি nested লুপ । nested লুপের মধ্যে ২টি instruction রয়েছে, ১টি হচ্ছে assignment এবং অপরটি হচ্ছে addition.
যদি n এর মান 1 হয় তাহলে প্রোগ্রামটির মোট instruction execution হবেঃ 1 x 1 x 2 = 2
যদি n এর মান 10 হয় তাহলে প্রোগ্রামটির মোট instruction execution হবেঃ 10 x 10 x 2 = 200
যদি n এর মান 100 হয় তাহলে প্রোগ্রামটির মোট instruction execution হবেঃ 100 x 100 x 2 = 20000
উপরের হিসাব গুলো দেখে আমরা বলতেই পারি যে আমাদের এই প্রোগ্রামটি n এর মানের উপর নির্ভর করবে।
দেখা যাচ্ছে যে n এর মানের উপর নির্ভর করে আমাদের এই প্রোগ্রামটির টাইম Complexity অনেক বেড়ে যাবে।
তাহলে আমাদের এই প্রোগ্রামটির Complexity হবেঃ O(n^2*2) => O(n^2) [উচ্চারন করতে, order of n square]
এখানে constant 2 কে আমরা বাদ দিয়ে দিতে পারি।

কিছু টার্ম যা আমাদের কে সাধারনত কোড লিখার সময় মনে রাখতে হবেঃ

১. সাধারনত n^2 অথবা n^3 পর্যন্ত সীমাবদ্ধ থাকার চেষ্টা করব। কারন এর বেশি হয়ে গেলে আমাদের প্রোগ্রামটি অনেক বেশি সময় লাগাবে যা আমাদের প্রোগ্রামের efficiency কে নষ্ট করে ফেলবে।

২. কমপ্লেক্সিটি হিসাবের সময় constant factor গুলোকে বাদ দিয়ে দিতে পাড়ি।

৩. O( n^2 + n ) => O(n^2) এখানে n^2 এর মান অবশ্যই n এর তুলনায় অনেক বড়। তাই O(n) কে বাদ দিয়ে দিতে পারি সহজেই।

৪. O(4n + n^3 + n^2) => O(n^3) একই ভাবে, এখানে n^3 এর মান অবশ্যই n^2, এবং 4n এর তুলনায় অনেক বড়। তাই n^2, এবং 4n কে বাদ দিয়ে দিতে পারি সহজেই।