Big-O notation / Time Complexity / Space Complexity

- Big-O notation은 알고리즘의 performance를 이야기 할 때 좋은 방법이다. 

O(1) < O(log n) < O(n) < O(n log n) < O(n^2)

Good                                                Bad

---

- Example - O(1)

public void printFirstItem(int[] arrayOfItems) { System.out.println(arrayOfItems[0]); }

Other examples : 1. Push, Pop on Stack 2. Access hash table

Tip: 

nO(1) = O(1)  // 앞의 상수n은 신경쓰지 않는다!!

2*O(1) = 10*O(1) = O(1) 

---

- Example - O(log n)

Binary Search Tree Access, Search, Insertion, Deletion

Denote n = 8

log8 = log2^3 = 3  // Binary search 라서 밑이 2인듯!

Tip:

nO(log n) = O(log n)

2*O(log n) = 10*O(log n) = O(log n)

---

- Example - O(n)

public void printAllItem(int[] arrayOfItems) { for (int item : arrayOfItems) { System.out.println(item); } }

Other examples:

- traverse tree

- traverse linked list

Tip:

nO(n) = O(n)

2*O(n) = 10*O(n) = O(n)

---

- Example - O(nlog n)

Quick Sort, Merge Sort, Heap Sort

Denote n=4

log8 = 2*log2^2 = 4 / Tip: nO(nlog n) = O(nl ogn)

Merge sort just divide the array in two halves at each stage which gives it log(n) component and the other N component comes from its comparisons that are made at each stage. So combining it becomes nearly O(n log n)

---

- Example - O(n^2)

public void printAllPossibleOrderdPairs(int[] arrayOfItems){ for (int firstItem : arrayOfItems) { for(int secondItem : arrayOfItems) { int[] orderPair = new int[]{firstItem, secondItem}; System.out.println(Arrays.toString(orderedPair)); } } }

Other examples:

- Insertion Sort

- Bubble Sort

- Selection Sort

Tip: nO(n^2) = O(n^2)

reference : 상상개발자