Time Complexity Summary
CS141-CS240-
IT245
Data
Structures
Moussa Academy
00201007153601
[Link]
Table of Contents
I. Notations ..................................................................................................................................................... 2
II. Rules for Time Complexity Problems (Find Big-O) ...................................................................................... 2
III. Simple Examples on Rules ....................................................................................................................... 3
IV. Complexity of Common Data Structures (LinkedList, Queue, Stack) ...................................................... 4
ArrayList vs LinkedList Implementation Comparison .................................................................................. 4
LinkedList Implementation Summary.......................................................................................................... 4
Stack Summary ............................................................................................................................................ 4
Queue Summary .......................................................................................................................................... 4
Tree Traversal Summary .............................................................................................................................. 5
V. Complexity of Common Algorithms ............................................................................................................ 6
1|Page [Link]
00201007153601
I. Notations
Rate of Growth vs 1. They are opposites
Running Time 2. Rate of growth: how fast a function growth with input size
• Big O (O()): Rate of Growth = WORST CASE/Upper Bound
Big O, Big Omega, • Omega (Ω()): Rate of Growth = BEST CASE/Lower Bound
Big Theta
• Theta (Θ()): Rate of Growth = AVERAGE CASE/Exact Bound
II. Rules for Time Complexity Problems (Find Big-O)
1. Assignment/Declaration O(1)
Sum/Minus
2. Loops Running time of statements inside body * number of iterations (n)
3. Nested Loops Running time of statement * size of all loops (n*n = n2 for two nested loops)
4. Consecutive Statements Take largest power. Example: if we have one loop, then two nested loops
O(n) then O(n2) Take O(n2)
5. If/else Running time of test + larger part (if or else) running time
6. Method Calls Always analyze methods first.
7. Recursive Methods If it is equal to a normal iterative loop O(n)
8. Loop Variables */ by O(log (n)) (example: for (int i =1 ; i <=n; i *= c)
Constant
9. Loop Variables O(log(log (n))) (example: for (int i =2 ; i <=n; i = pow(i, c))
increased/reduced
exponentially
2|Page [Link]
00201007153601
III. Simple Examples on Rules
So, final answer is O6N+5) = O(N)
3|Page [Link]
00201007153601
IV. Complexity of Common Data Structures (LinkedList, Queue,
Stack)
ArrayList vs LinkedList Implementation Comparison
ArrayList LinkedList
1. Adding item at END O(N) O(N)
2. Adding items at FRONT O(N2) O(N)
3. Compute SUM O(N) O(N2)
LinkedList Implementation Summary
Data Structure Operation Worst Cases: Big-O Notation
Search • Worst Case: When value not found
• O(N)
Delete • Worst Case: When value not found
Linked List
• O(N)
Insert (at end) • O(N)
Insert (at front) • O(N)
Stack Summary
• We can implement stack using LinkedList or ArrayList
Data Structure Operation Worst Cases: Big-O Notation
Push • O(1)
Stack Pop • O(1)
Peek • O(1)
Queue Summary
• We can implement Queue using LinkedList or ArrayList
Data Structure Operation Worst Cases: Big-O Notation
Enqueue • O(1)
Queue Dequeue • O(1)
Peek • O(1)
4|Page [Link]
00201007153601
Tree Traversal Summary
• Depth of Perfect Tree: O (Log N)
Preoder Inorder Postorder
O(N) O(N) O(N)
5|Page [Link]
00201007153601
V. Complexity of Common Algorithms
Algorithm Case Value
Worst Case • O(N )
2
Insertion Sort
Best Case • Ω (N)
Shellsort Worst Case • O(N2)
Best Case • Ω (N LogN)
Worst Case (using Hibbard Increments) • O(N3/2)
Heapsort Worst Case • 2N Log N – O(N)
Merge Sort Worst Case • O (N Log N)
Quick Sort Worst Case • O(N2)
Average Case • Θ (N LogN)
Worst Case (Combine Quick & Heapsort) • O(N Log N)
6|Page [Link]
00201007153601
