বড় O লিখনপদ্ধতি

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

O প্রতীকটি অপর একটি সরলতর ফাংশনের সাপেক্ষে কোন ফাংশনের মানের অসীমতটীয় ঊর্ধ্বসীমা নির্দেশ করে। এছাড়া o, Ω, ω, ও Θ প্রতীকগুলি অন্যান্য ঊর্ধ্ব, নিম্ন, বা বদ্ধ সীমা নির্দেশ করে।

সাধারণ সংজ্ঞা

ধরা যাক f(x) ও g(x)) বাস্তব সংখ্যা সেটের কোনো উপসেটের উপর সংজ্ঞাত x এর দুটি ফাংশন (function)। তাহালে আমরা লিখতে পারি,

$f(x)=O(g(x)){\mbox{ as }}x\to \infty \,$

যদি এবং কেবলমাত্র যদি (if and only if) x এর যথেষ্ট বড় (sufficiently large) মানের জন্য, প্রকৃ্ত মানের (absolute value)বিচারে g(x) খুব বেশী হলে f(x) এর কোনো ধ্রুবক গুণ পরিমাণ (constant times)। অরথাৎ, f(x) = O(g(x)) যদি এবং কেবলমাত্র যদি এমন একটি ধনাত্মক বাস্তব সংখ্যা M এবং একটি বাস্তব সংখ্যাx₀ পাওয়া যায় যার জন্য,

$|f(x)|\leq \;M|g(x)|{\mbox{ for all }}x>x_{0}.$

আনেক ক্ষেত্রে, যখন আমরা বৃ্দ্ধি হার (growth rate) এর উপর কাজ করি এবং যখন x অসীমের দিকে ধাবমান হয়, তখন এটুকু বলাই যথেষ্ট যে, f(x) = O(g(x)).

এই প্রতীকটি অনেক সময়েই কোনো বাস্তব সংখ্যা aএর নিকটে f এর প্রকৃতি নির্ধারণের কাজে ব্যবহৃত হয়ে থাকে। (প্রায়েই, a  = 0): আমরা তখন বলিঃ

ব্যবহার

এটি গণিতে সাধারণত কোন কর্তিত অসীম ধারার অবশিষ্ট রাশির আচরণ বর্ণনায় ব্যবহৃত হয়।

কম্পিউটার বিজ্ঞানে এটি অ্যালগোরিদমসমূহের বিশ্লেষণে অ্যালগোরিদমের জটিলতা নির্ণয়ে ব্যবহৃত হয়।

এই লিখনপদ্ধতিটি সর্বপ্রথম উল্লেখ করেন জার্মান সংখ্যাতাত্ত্বিক পাউল বাখমান, ১৮৯৪ সালে তাঁর রচিত Analytische Zahlentheorie (আনালিটিশে ৎসালেনটেওরি বিশ্লেষণী সংখ্যাতত্ত্ব) বইটির দ্বিতীয় খণ্ডে। পরবর্তীতে জার্মান সংখ্যাতাত্ত্বিক এডমুন্ড লান্ডাউ লিখনপদ্ধতিটির ব্যাপক ব্যবহার করেন এবং এজন্য O-কে কখনো কখনো লান্ডাউ প্রতীক নামেও ডাকা হয়।