O(1) vs O(n) মানে কি? 

আমরা অনেক সময় প্রব্লেম সল্ভিং করার সময় complexity নামে একটা জিনিস শুনে থাকি। Time complexity আর Space complexity বুঝাতে আমরা এগুলা ব্যবহার করি । এগুলার মানে আসলে কি?




ধরা যাক, আমি এক বক্স আইসক্রিম এনে তোমার সামনে রাখলাম। এখন বললাম বক্সে কি কোনো আইসক্রিম আছে নাকি আমি সব খেয়ে শেষ করে ফেলেছি? এখন এটা বুঝার জন্য তুমি দুইটা কাজ করতে পারো । বক্স ধরে একটা ঝাঁকি দিতে পারো, কিংবা বক্স খুলে, গুনে দেখতে পারো মোট কয়টা আছে। এখানে বিষয় হল, যদি বক্সে ১ টা থাকুক আর ১০ টা থাকুক ঝাঁকি দিয়ে বুঝার জন্য একবার ঝাঁকি দেয়াই যথেষ্ট। মানে, আইসক্রিমের সংখ্যা বাড়া কমার সাথে এর কোন সম্পর্ক নেই।



একবার ঝাঁকি দিলেই আমরা এটা বুঝে যাবো। কিন্তু যদি তুমি বোকার মতো বক্স খুলে গুনতে শুরু কর, এবং গুনা শেষ হলে বল, যেহেতু এত্তগুলা আইসক্রিম আছে, তাই বক্সে আইসক্রিম আছে, প্রমাণিত। এই ক্ষেত্রে ১ টা আইসক্রিম অবশিষ্ট থাকলে সময় খুব বেশি লাগবে না। কিন্তু যদি ৫-১০ টা কিংবা আরো বেশি থাকে তাহলে কি হবে?



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



কেন? কারণ সময় কম লাগছে। কষ্ট কম করতে হচ্ছে। তেমনি আমরা যখন কম্পিউটারকে কোন কিছু সল্ভ করতে দেই, তখন চেষ্টা করি কত কম সময়ে, কম রিসোর্স ব্যবহার করে কাজটা করা যায়।



এখানে আমাদের প্রথম ওয়েতে Time complexity হল O(1), কারণ একবার ঝাঁকি দিলেই হবে। কতগুলা আইসক্রিম এটা কোন বিষয় না। কিন্তু দ্বিতীয় ওয়েতে Time complexity হল O(n)। কারণ, n সংখ্যক আইসক্রিম গুনতে n টাইম লাগবে।



খুব সহজভাবে বললে এটাকেই Time complexity বলে। অন্যদিকে Space complexity হল, মেমোরি ব্যবহারের উপর। আইডিয়া একই রকম। উপরের বিষয়ের খুব সহজ উদাহরণ হল array এর ভিতরে কোন item আছে কি বা নেই এটা চেক করার ওয়ে। দুইভাবে করা যায়। array.isEmpty, array.count > 0।



এখন যদি তুমি উপরের উদাহরণ বুঝে থাকো, তাহলে খুবই সহজেই বলতে পারবে, array.isEmpty হল O(1) এবং পরেরটা O(n)। এটার একটা কেতাবি নাম আছে Big O Notation