Big O Notation

algorithms big-o performance computer-science

September 1, 2026

9 minutes to read

0 views

Big O Notation

Big O Notation ဆိုတာ ဘာလဲ?

Application တစ်ခုမှာ Data အနည်းငယ်ရှိတဲ့အချိန် Code က မြန်နေပေမယ့် Data သန်းနဲ့ချီလာတဲ့အခါ အဲ့ဒီ Code က အရမ်းနှေးသွားနိုင်ပါတယ်။ ဥပမာ User 10 ယောက်ရှိတဲ့ Array တစ်ခုကို Loop ပတ်တာနဲ့ User 10 Million ရှိတဲ့ Array တစ်ခုကို Loop ပတ်တာဟာ အချိန်တူမှာ မဟုတ်ပါဘူး။

ဒီလို Input Size ကြီးလာတာနဲ့အမျှ Algorithm တစ်ခုရဲ့ လုပ်ဆောင်ရမယ့် workload ဘယ်လောက်မြန်မြန် တိုးလာသလဲဆိုတာကို ဖော်ပြဖို့ Big O Notation ကို အသုံးပြုပါတယ်။

Big O က Code တစ်ခု Run ဖို့ 2ms ဒါမှမဟုတ် 5 seconds ကြာမယ်ဆိုတာကို တိုင်းတာတာ မဟုတ်ပါဘူး။ Input Size ကြီးလာတဲ့အခါ Algorithm ရဲ့ Growth Rate ဘယ်လိုပြောင်းလဲသလဲဆိုတာကို ဖော်ပြတာ ဖြစ်ပါတယ်။

Time Complexity

Algorithm တစ်ခုရဲ့ Input Size ကြီးလာတာနဲ့အမျှ လုပ်ဆောင်ရမယ့် Operation အရေအတွက် ဘယ်လောက်တိုးလာသလဲဆိုတာကို Time Complexity လို့ ခေါ်ပါတယ်။ Input Size ကို ပုံမှန်အားဖြင့် n နဲ့ ကိုယ်စားပြုပါတယ်။

for (const user of users) {
  console.log(user);
}

users ထဲမှာ User 10 ယောက်ရှိရင် Loop က 10 ကြိမ်ခန့် Run ရပါမယ်။ User 1,000 ရှိရင် 1,000 ကြိမ်ခန့် Run ရပါမယ်။

Input Size တိုးလာတာနဲ့ workload ကလည်း တိုက်ရိုက်တိုးလာတဲ့အတွက် ဒီ Algorithm ရဲ့ Time Complexity က O(n) ဖြစ်ပါတယ်။

O(1) — Constant Time

Input Size ဘယ်လောက်ကြီးလာလာ Operation အရေအတွက်က Input Size နဲ့အတူ မတိုးလာဘူးဆိုရင် O(1) လို့ ခေါ်ပါတယ်။

const firstUser = users[0];

Array ထဲမှာ User 10 ယောက်ရှိရှိ၊ 10 Million ရှိရှိ First Element ကို Index နဲ့ Access လုပ်တာက တူညီတဲ့ Operation ပုံစံနဲ့ လုပ်ဆောင်နိုင်ပါတယ်။

10 items          → 1 operation
1,000 items       → 1 operation
1,000,000 items   → 1 operation

ဒါကြောင့် O(1) ကို Constant Time လို့ ခေါ်ပါတယ်။

O(log n) — Logarithmic Time

Input Size ကြီးလာပေမယ့် Search လုပ်ရမယ့် Data ကို Step တစ်ခုစီမှာ အများကြီး လျှော့ချနိုင်တဲ့ Algorithm တွေမှာ O(log n) ကို တွေ့ရပါတယ်။ အကောင်းဆုံး Example က Binary Search ဖြစ်ပါတယ်။

Sorted Array တစ်ခုထဲမှာ Value တစ်ခု ရှာတဲ့အခါ Element တစ်ခုချင်းစီကို လိုက်မရှာဘဲ အလယ်ကနေ စပြီး Search Space ကို တစ်ဝက်စီ လျှော့သွားပါတယ်။

1,000,000 items
       ↓
500,000
       ↓
250,000
       ↓
125,000
       ↓
62,500
       ↓
...

ဒါကြောင့် Data အရမ်းများလာရင်တောင် လိုအပ်တဲ့ Step အရေအတွက်က နှေးနှေးပဲ တိုးလာပါတယ်။ ဒီလို Algorithm ကို O(log n) လို့ ခေါ်ပါတယ်။

O(n) — Linear Time

Input Size တိုးလာတာနဲ့ Operation အရေအတွက်လည်း အချိုးကျ တိုးလာတာကို O(n) လို့ ခေါ်ပါတယ်။

function findUser(users, id) {
  for (const user of users) {
    if (user.id === id) {
      return user;
    }
  }
}

Worst Case မှာ ရှာနေတဲ့ User က Array ရဲ့ နောက်ဆုံးမှာ ရှိနိုင်တာကြောင့် User အားလုံးကို စစ်ရနိုင်ပါတယ်။

10 users        → up to 10 checks
100 users       → up to 100 checks
1,000 users     → up to 1,000 checks

Input နှစ်ဆတိုးရင် Work လည်း အကြမ်းဖျင်း နှစ်ဆတိုးလာတာကြောင့် Linear Time ဖြစ်ပါတယ်။

O(n log n) — Linearithmic Time

O(n log n) ကို Efficient Sorting Algorithm တွေမှာ မကြာခဏ တွေ့ရပါတယ်။

Merge Sort
Heap Sort
Efficient Comparison-based Sorting Algorithms

ဒီ Algorithm တွေက Data အားလုံးကို Process လုပ်ရပေမယ့် Problem ကို အပိုင်းငယ်တွေ ခွဲပြီး Efficient ဖြစ်အောင် ဖြေရှင်းတာကြောင့် O(n²) ထက် အများကြီး ပိုကောင်းပါတယ်။

Programming Language တွေရဲ့ Built-in sort() Function တွေရဲ့ Complexity ကတော့ Runtime နဲ့ Implementation ပေါ်မူတည်နိုင်တာကြောင့် O(n log n) လို့ အမြဲတမ်း သတ်မှတ်လို့ မရပါဘူး။

O(n²) — Quadratic Time

Loop တစ်ခုအတွင်းမှာ နောက်ထပ် Loop တစ်ခုရှိတဲ့ Nested Loop တွေမှာ O(n²) ကို မကြာခဏ တွေ့ရပါတယ်။

for (const user of users) {
  for (const otherUser of users) {
    console.log(user.id, otherUser.id);
  }
}

User 10 ယောက်ရှိရင် Operation က အကြမ်းဖျင်း

10 × 10 = 100

ဖြစ်ပါတယ်။ User 1,000 ရှိလာရင်

1,000 × 1,000 = 1,000,000

ဖြစ်သွားပါတယ်။

ဒါကြောင့် O(n²) Algorithm တွေဟာ Input Size ကြီးလာတာနဲ့ Performance အရမ်းမြန်မြန် ကျဆင်းလာနိုင်ပါတယ်။

O(2ⁿ) နဲ့ O(n!)

O(2ⁿ) နဲ့ O(n!) ဟာ Input Size အနည်းငယ်တိုးတာနဲ့ Operation အရေအတွက် အလွန်မြန်မြန် တိုးလာတဲ့ Complexity တွေ ဖြစ်ပါတယ်။ Brute-force Algorithm၊ Combination၊ Permutation နဲ့ Recursive Problem တချို့မှာ ဒီ Complexity တွေကို တွေ့နိုင်ပါတယ်။

O(2ⁿ)   → Exponential

O(n!)   → Factorial

Input Size ကြီးတဲ့အခါ ဒီလို Algorithm တွေကို Production System မှာ တိုက်ရိုက်အသုံးပြုဖို့ မသင့်တော်နိုင်တာကြောင့် ပိုကောင်းတဲ့ Algorithm ဒါမှမဟုတ် Optimization Strategy ကို ရှာဖို့ လိုအပ်ပါတယ်။

Big O Comparison

Big O	Name	Growth
`O(1)`	Constant	Excellent
`O(log n)`	Logarithmic	Excellent
`O(n)`	Linear	Good
`O(n log n)`	Linearithmic	Good
`O(n²)`	Quadratic	Slow for large input
`O(2ⁿ)`	Exponential	Very Slow
`O(n!)`	Factorial	Extremely Slow

ယေဘုယျအားဖြင့် Growth Rate ကို ဒီလို စဉ်းစားနိုင်ပါတယ်။

O(1)
 ↓
O(log n)
 ↓
O(n)
 ↓
O(n log n)
 ↓
O(n²)
 ↓
O(2ⁿ)
 ↓
O(n!)

အောက်ဘက်ကို ဆင်းလာလေလေ Input ကြီးလာတဲ့အခါ workload ကလည်း ပိုမြန်မြန် တိုးလာလေလေ ဖြစ်ပါတယ်။

Big O ကို ဘယ်လိုတွက်မလဲ?

Big O ကို စတွက်တဲ့အခါ Code ထဲက Operation တွေဟာ Input Size နဲ့အတူ ဘယ်လို တိုးလာသလဲဆိုတာ ကြည့်ရပါတယ်။ Loop တစ်ခုဆိုရင်

for (const user of users) {
  console.log(user);
}

O(n) ဖြစ်ပါတယ်။ Nested Loop ဆိုရင်

for (const user of users) {
  for (const otherUser of users) {
    console.log(user, otherUser);
  }
}

O(n²) ဖြစ်ပါတယ်။ ဒါပေမယ့် Nested Loop တိုင်း O(n²) မဟုတ်ပါဘူး။

for (const user of users) {
  for (const product of products) {
    // ...
  }
}

users ရဲ့ Size ကို n၊ products ရဲ့ Size ကို m လို့ သတ်မှတ်မယ်ဆိုရင် Complexity က

O(n × m)

ဖြစ်ပါတယ်။ Independent Input နှစ်ခုဖြစ်တာကြောင့် O(n²) လို့ တိုက်ရိုက် သတ်မှတ်လို့ မရပါဘူး။

Constants တွေကို ဘာကြောင့် ဖယ်လိုက်တာလဲ?

ဒီ Code ကို ကြည့်ပါ။

for (const user of users) {
  console.log(user.name);
}

for (const user of users) {
  console.log(user.email);
}

Loop နှစ်ခုရှိတဲ့အတွက် Operation က 2n လောက် ဖြစ်ပါတယ်။

O(2n)

ဒါပေမယ့် Big O မှာ Constant ကို အဓိက မကြည့်ပါဘူး။

O(2n) → O(n)

Input အရမ်းကြီးလာတဲ့အခါ Algorithm ရဲ့ Growth Rate ကို အဓိက စိတ်ဝင်စားတာကြောင့် Constant တွေကို ဖယ်ထားပါတယ်။

Lower-order Terms

Algorithm တစ်ခုရဲ့ Operations က

n² + n + 10

ဖြစ်တယ်ဆိုပါစို့။ Big O မှာ

O(n² + n + 10)

↓

O(n²)

လို့ ရေးပါတယ်။

Input Size အရမ်းကြီးလာတဲ့အခါ n² က ကျန်တဲ့ n နဲ့ 10 ထက် အများကြီး ပိုမြန်မြန် ကြီးလာတာကြောင့် Dominant Term ကိုပဲ အဓိကထားတာ ဖြစ်ပါတယ်။

Space Complexity

Algorithm Performance ကို Time တစ်ခုတည်းနဲ့ မတိုင်းတာပါဘူး။ Algorithm တစ်ခု Run ဖို့ Additional Memory ဘယ်လောက်လိုအပ်သလဲဆိုတာကို Space Complexity လို့ ခေါ်ပါတယ်။

function sum(numbers) {
  let total = 0;

  for (const number of numbers) {
    total += number;
  }

  return total;
}

Input ကြီးလာပေမယ့် total လို Additional Variable အနည်းငယ်ပဲ လိုအပ်တာကြောင့် Extra Space က O(1) ဖြစ်ပါတယ်။

function double(numbers) {
  const result = [];

  for (const number of numbers) {
    result.push(number * 2);
  }

  return result;
}

Input Size တိုးလာတာနဲ့ result Array ရဲ့ Size လည်း တိုးလာတာကြောင့် Additional Space က O(n) ဖြစ်ပါတယ်။

Data Structure နဲ့ Big O

Data Structure ရွေးချယ်မှုက Algorithm Performance ကို အများကြီး သက်ရောက်နိုင်ပါတယ်။ ဥပမာ User ကို ID နဲ့ ရှာမယ်ဆိုပါစို့။ Array ကို Loop ပတ်ပြီး ရှာရင်

const user = users.find((user) => user.id === id);

Worst Case မှာ User အားလုံးကို စစ်ရနိုင်တဲ့အတွက် O(n) ဖြစ်ပါတယ်။ Hash Map ကို အသုံးပြုထားရင်

const usersById = new Map();

usersById.set("user-1", {
  name: "John",
});

const user = usersById.get("user-1");

Hash-based Lookup ဟာ ပုံမှန်အားဖြင့် Average O(1) နဲ့ ရှာနိုင်ပါတယ်။

ဒါကြောင့် Algorithm ကို Optimize လုပ်တဲ့အခါ Loop လျှော့တာတင်မဟုတ်ဘဲ သင့်တော်တဲ့ Data Structure ရွေးချယ်တာလည်း အရေးကြီးပါတယ်။

Real-world Example

User List နဲ့ Account List နှစ်ခုကို userId နဲ့ Match လုပ်ချင်တယ်ဆိုပါစို့။ အရိုးရှင်းဆုံးနည်းက Nested Loop ဖြစ်ပါတယ်။

for (const user of users) {
  for (const account of accounts) {
    if (user.id === account.userId) {
      console.log(user, account);
    }
  }
}

users နဲ့ accounts နှစ်ခုလုံးမှာ n ခုစီရှိတယ်လို့ ယူဆရင် Complexity က O(n²) ဖြစ်နိုင်ပါတယ်။ Data 100 ခုမှာ သိသာချင်မှ သိသာပေမယ့် Data သန်းနဲ့ချီလာရင် Problem ဖြစ်လာနိုင်ပါတယ်။

Account တွေကို အရင်ဆုံး Hash Map အဖြစ် ပြောင်းထားနိုင်ပါတယ်။

const accountsByUserId = new Map();

for (const account of accounts) {
  accountsByUserId.set(account.userId, account);
}

for (const user of users) {
  const account = accountsByUserId.get(user.id);

  if (account) {
    console.log(user, account);
  }
}

ပထမ Loop က O(m) ဖြစ်ပြီး ဒုတိယ Loop က O(n) ဖြစ်ပါတယ်။ ဒါကြောင့် Overall Complexity က

O(n + m)

ဖြစ်သွားပါတယ်။

ဒီ Example က Data Structure မှန်မှန်ရွေးချယ်ခြင်းနဲ့ Algorithm Design ပြောင်းလဲခြင်းက Performance ကို ဘယ်လောက်အထိ ပြောင်းလဲနိုင်သလဲဆိုတာ ပြသပါတယ်။

Big O ရဲ့ Limitations

Big O နည်းတဲ့ Algorithm တိုင်း လက်တွေ့မှာ အမြဲတမ်း ပိုမြန်မယ်လို့ မဆိုလိုပါဘူး။ O(n) Algorithm တစ်ခုမှာ Operation တစ်ခုချင်းစီက အရမ်း Expensive ဖြစ်နေရင် Input အသေးတစ်ခုအတွက် O(n²) Algorithm တစ်ခုထက်တောင် ပိုနှေးနိုင်ပါတယ်။

Real-world Performance ကို အောက်ပါအချက်တွေကလည်း သက်ရောက်စေပါတယ်။

CPU
Memory
Cache
Network
Database
Disk I/O
Implementation
Input Size

ဒါကြောင့် Big O ကို Performance ကို အတိအကျတိုင်းတာတဲ့ Tool အဖြစ် မမြင်သင့်ဘဲ Algorithm တစ်ခု Scale ဘယ်လိုလုပ်မလဲ ဆိုတာကို Reason လုပ်ဖို့ အသုံးပြုတဲ့ Tool အဖြစ် နားလည်သင့်ပါတယ်။

Production Performance Problem တစ်ခုကို ဖြေရှင်းတဲ့အခါ Big O ကို စဉ်းစားသလို Profiling နဲ့ Measurement ကိုလည်း အတူအသုံးပြုသင့်ပါတယ်။

Developer တွေ Big O ကို ဘာကြောင့် နားလည်သင့်လဲ?

Application အသေးတစ်ခုမှာ Algorithm Efficiency က သိသာချင်မှ သိသာပါလိမ့်မယ်။ ဒါပေမယ့် User အရေအတွက်၊ Database Record အရေအတွက်နဲ့ Request Volume တွေ တိုးလာတဲ့အခါ Inefficient Algorithm တွေဟာ Performance Problem ဖြစ်လာနိုင်ပါတယ်။

Big O ကို နားလည်ထားရင် Nested Loop တစ်ခုရဲ့ Cost ကို သတိထားနိုင်တယ်၊ Search နဲ့ Sorting Algorithm တွေကို ပိုကောင်းစွာ ရွေးချယ်နိုင်တယ်၊ Data Structure မှန်ကို အသုံးပြုနိုင်ပြီး Code တစ်ခု Data ကြီးလာတဲ့အခါ ဘယ်လို Scale ဖြစ်မလဲဆိုတာကို ကြိုတင်စဉ်းစားနိုင်ပါတယ်။

အကျဉ်းချုပ်အားဖြင့် Big O Notation ဆိုတာ Algorithm တစ်ခု Run ဖို့ အချိန်ဘယ်လောက်ကြာမယ်ဆိုတာကို တိုင်းတာတာ မဟုတ်ဘဲ Input Size ကြီးလာတဲ့အခါ Time နဲ့ Space Requirement တွေ ဘယ်လို Growth ဖြစ်လာမလဲဆိုတာကို ဖော်ပြတဲ့ နည်းလမ်း ဖြစ်ပါတယ်။ O(1)၊ O(log n)၊ O(n)၊ O(n log n) နဲ့ O(n²) စတဲ့ Complexity တွေကို နားလည်ထားခြင်းအားဖြင့် Developer တစ်ယောက်ဟာ Algorithm နဲ့ Data Structure တွေကို ပိုကောင်းစွာ ရွေးချယ်နိုင်ပြီး Data ကြီးလာတဲ့အခါလည်း Scale လုပ်နိုင်တဲ့ Application တွေကို တည်ဆောက်နိုင်မှာ ဖြစ်ပါတယ်။