Java Notes
HubArray IntroductionArray OperationsArray Programs — FundamentalsArray Interview QuestionsJagged Array in JavaMulti Dimensional ArrayOne Dimensional Arraybreak and continue in JavaDo-While Loop in JavaFor Loop in JavaIf-Else Statements in JavaNested Loops in JavaSwitch-Case in JavaWhile Loop in JavaJava Compilation ProcessFeatures of JavaYour First Java ProgramHistory of JavaJava EditionsJava Program StructureJDK, JRE, and JVMWhat is Java?Immutable Strings in JavaString Class in JavaString Interview QuestionsString MethodsString Programs — FundamentalsStringBuffer in JavaStringBuilder in JavaComments in JavaData Types in JavaIdentifiers in JavaInput and Output in JavaKeywords in JavaOperators in JavaType Casting in JavaVariables in JavaAbstract Class in JavaAbstraction in JavaAnonymous Class in JavaClass and Object in JavaConstructor in JavaEncapsulation in JavaInheritance in JavaInner Class in JavaInterface in JavaMethod Overloading in JavaMethod Overriding in JavaObject Class in JavaObject Cloning in JavaOOPs IntroductionPolymorphism in Javastatic Keyword in Javasuper Keyword in Javathis Keyword in JavaWrapper Class in JavaCollections Framework OverviewCollections Practice ProgramsComparable vs Comparator in JavaGenerics in JavaIterator in JavaArrayList in JavaLinkedList in JavaStack in Java — Collections FrameworkVector in JavaHashMap in JavaHashtable in JavaLinkedHashMap in JavaTreeMap in JavaArrayDeque in JavaDeque Interface in JavaPriorityQueue in JavaHashSet in JavaLinkedHashSet in JavaTreeSet in JavaException Handling Best PracticesCustom Exceptions in JavaException Hierarchy in JavaFinally Block in JavaException Handling Introductionthrow and throws Keywords in JavaTry-Catch Block in JavaBuffered Streams in JavaByte Streams in JavaCharacter Streams in JavaDeserialization in JavaFile Class in JavaJava NIO PackageSerialization in JavaDate and Time API in Java 8Default and Static Methods in InterfacesFunctional Interface in Java 8Lambda Expression in Java 8Method Reference in Java 8Optional Class in Java 8Stream API in Java 8Creating Threads in JavaDaemon Threads in JavaExecutor Framework in JavaInter-Thread Communication in JavaMultithreading Programs in JavaRunnable Interface in JavaSynchronization in JavaThread Class in JavaThread IntroductionThread Life Cycle in JavaThread Priority in JavaBatch Processing in JDBCCallableStatement in JDBCJDBC ArchitectureJDBC IntroductionJDBC ProjectsMySQL Connection with JDBCPreparedStatement in JDBCResultSet in JDBCStatement Interface in JDBCTransaction Management in JDBCCookies in ServletsExpression Language (EL)GenericServletHttpServletJSP IntroductionJSP Tags and JSTLMVC ArchitectureRequest and Response ObjectsServlet IntroductionServlet Life CycleSession TrackingDependency InjectionAPI GatewayConfig ServerDocker DeploymentEureka Server - Service DiscoverySpring BeansCRUD ApplicationException Handling in Spring BootJWT Authentication — Java ProgrammingREST API with Spring BootSpring SecuritySpring Boot IntroductionSpring Data JPAValidation in Spring BootSpring Core ContainerSpring Framework IntroductionDynamic Programming in JavaGraph Data Structure in JavaHashing in JavaHeap (DSA)Linked List in JavaQueue in JavaRecursion in JavaSearching Algorithms in JavaSorting Algorithms in JavaStack in Java — DSA in JavaTime ComplexityTree Data Structure in JavaAdapter Design PatternBuilder Design PatternFactory Design PatternMVC Pattern — Java ProgrammingObserver Design PatternSingleton Design PatternArray Programs — PracticeBasic Java ProgramsCollection ProgramsJDBC ProgramsMultithreading ProgramsOOP ProgramsPlacement Coding QuestionsString Programs — PracticeBanking System — Java ProgrammingChat ApplicationE-Commerce BackendEmployee Management SystemLibrary Management System — Java ProgrammingSpring Boot Fullstack ProjectStudent Management System — Java ProgrammingCoding Interview QuestionsCollections Interview QuestionsCore Java Interview QuestionsJDBC Interview QuestionsMultithreading Interview QuestionsOOPs Interview QuestionsSpring Framework Interview QuestionsJava Cheat SheetImportant Formulas & ConceptsImportant Java ProgramsQuick Revision Notes — Java ProgrammingJava Master Course - Learning Roadmap
Master time and space complexity — Big O notation, analyzing algorithms, common complexity classes, amortized analysis, and practical comparison with Java examples.
What is Time Complexity?
Time complexity describes how the runtime of an algorithm grows as the input size increases. It's not about exact time — it's about the rate of growth.
| Input size | n = 1,000,000 |
| O(1) | 1 operation (instant) |
| O(log n) | 20 operations (instant) |
| O(n) | 1,000,000 ops (milliseconds) |
| O(n log n) | 20,000,000 ops (seconds) |
| O(n²) | 1,000,000,000,000 (hours/days) |
| O(2^n) | impossible (heat death of universe) |
Analyzing Code — Rules
Rule 1: Drop Constants
Example
// O(2n) → O(n)
for (int i = 0; i < n; i++) { } // n
for (int i = 0; i < n; i++) { } // + n = 2n → O(n)
// O(n/2) → O(n)
for (int i = 0; i < n; i += 2) { } // n/2 → O(n)
Rule 2: Drop Lower-Order Terms
Example
// O(n² + n) → O(n²)
for (int i = 0; i < n; i++) { // O(n²)
for (int j = 0; j < n; j++) { }
}
for (int k = 0; k < n; k++) { } // + O(n) → still O(n²)
Rule 3: Different Inputs → Different Variables
java example
// O(a + b), NOT O(n)
void processTwo(int[] arrA, int[] arrB) {
for (int x : arrA) { } // O(a)
for (int y : arrB) { } // O(b)
} // Total: O(a + b)
// O(a * b), NOT O(n²)
void crossProduct(int[] arrA, int[] arrB) {
for (int x : arrA) { // O(a)
for (int y : arrB) { } // × O(b)
}
} // Total: O(a * b)Common Patterns
O(1) — Constant
Example
// Array access, HashMap get, stack push/pop
int getFirst(int[] arr) {
return arr[0]; // O(1) - same time regardless of array size
}
void swapElements(int[] arr, int i, int j) {
int temp = arr[i]; // O(1)
arr[i] = arr[j]; // O(1)
arr[j] = temp; // O(1)
} // Total: O(1)
O(log n) — Logarithmic
Example
// Binary search - halves input each step
int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) { // Runs log₂(n) times
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
// n=1024 → 10 iterations (log₂1024 = 10)
// n=1,000,000 → ~20 iterations
O(n) — Linear
Example
// Linear search, sum of array, finding max
int findMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) { // n-1 iterations
if (arr[i] > max) max = arr[i];
}
return max;
} // O(n)
O(n log n) — Linearithmic
java example
// Merge sort, quicksort (average), heap sort
void mergeSort(int[] arr, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid); // T(n/2)
mergeSort(arr, mid + 1, right); // T(n/2)
merge(arr, left, mid, right); // O(n)
}
}
// Recurrence: T(n) = 2T(n/2) + O(n) → O(n log n)O(n²) — Quadratic
Example
// Bubble sort, selection sort, checking all pairs
void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) { // n times
for (int j = 0; j < n - i - 1; j++) { // × n times (avg)
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
} // O(n²)
Space Complexity
Example
// O(1) space — in-place
void reverseArray(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++; right--;
}
} // Only uses fixed extra variables
// O(n) space — creates new array
int[] duplicateArray(int[] arr) {
int[] copy = new int[arr.length]; // n extra space
for (int i = 0; i < arr.length; i++) {
copy[i] = arr[i];
}
return copy;
}
// O(n) space — recursive call stack
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // n stack frames
}
Java Collections Complexity
| Operation | ArrayList | LinkedList | HashMap | TreeMap | HashSet |
|---|---|---|---|---|---|
| Access/Get | O(1) | O(n) | O(1)* | O(log n) | — |
| Search | O(n) | O(n) | O(1)* | O(log n) | O(1)* |
| Insert (end) | O(1)* | O(1) | O(1)* | O(log n) | O(1)* |
| Insert (mid) | O(n) | O(1)† | — | — | — |
| Delete | O(n) | O(1)† | O(1)* | O(log n) | O(1)* |
| Sort | O(n log n) | O(n log n) | — | — | — |
*amortized, †with iterator at position
Amortized Analysis
java example
// ArrayList.add() — usually O(1), occasionally O(n) when resizing
// But AMORTIZED over n operations: O(1) per operation
// Example: ArrayList grows by doubling
// Start: capacity 1
// Add 1 element: no resize, 1 operation
// Add 2nd: resize to 2, copy 1 + insert 1 = 2 ops
// Add 3rd: resize to 4, copy 2 + insert 1 = 3 ops
// Add 5th: resize to 8, copy 4 + insert 1 = 5 ops
// ...
// Total for n inserts ≈ 3n operations → O(1) amortized per insertPractical Comparison (Benchmark)
Example
public class ComplexityBenchmark {
public static void main(String[] args) {
int[] sizes = {1000, 10000, 100000, 1000000};
for (int n : sizes) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = i;
// O(1) - Array access
long start = System.nanoTime();
int val = arr[n/2];
long o1Time = System.nanoTime() - start;
// O(log n) - Binary search
start = System.nanoTime();
Arrays.binarySearch(arr, n/2);
long logNTime = System.nanoTime() - start;
// O(n) - Linear search
start = System.nanoTime();
for (int i = 0; i < n; i++) { if (arr[i] == n-1) break; }
long nTime = System.nanoTime() - start;
System.out.printf("n=%,10d | O(1)=%5dns | O(logn)=%7dns | O(n)=%10dns%n",
n, o1Time, logNTime, nTime);
}
}
}
Interview Questions
Q1: What is the difference between O(n) and O(n²)?
Answer: O(n) means runtime grows linearly (double input = double time). O(n²) means runtime grows quadratically (double input = 4× time). For n=1000: O(n)=1000 operations, O(n²)=1,000,000 operations.
Q2: What is the time complexity of HashMap.get() and why?
Answer: O(1) amortized. It computes hashCode, finds the bucket directly (O(1)), then checks equals in the bucket (usually O(1) if few collisions). Worst case with all collisions: O(n) for LinkedList chains, O(log n) for tree bins (Java 8+).
Q3: What is amortized time complexity?
Answer: The average time per operation over a sequence of operations. ArrayList.add() is O(1) amortized — most adds are O(1) but occasional resizing is O(n). Over n operations, total work is O(n), so per-operation average is O(1).
Q4: Why do we drop constants in Big O?
Answer: Big O describes growth rate, not exact time. O(2n) and O(n) grow at the same rate — both are linear. Constants depend on hardware and are meaningless for comparing algorithmic efficiency across different machines.
Q5: What is the time complexity of Arrays.sort() in Java?
Answer: O(n log n). For objects it uses TimSort (merge sort variant). For primitives it uses Dual-Pivot Quicksort. Both are O(n log n) average and worst case (TimSort) or O(n²) worst case (Quicksort, but extremely unlikely with pivot selection).
Q6: How do you determine if your algorithm is efficient enough?
Answer: Rule of thumb: ~10⁸ simple operations per second. For n=10⁵, O(n²)=10¹⁰ (too slow), O(n log n)=~10⁶ (fast). Match your algorithm's complexity to the constraint: n≤10⁶ needs O(n log n) or better; n≤10³ allows O(n²).
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Time Complexity.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.
Search Terms
java-master-course, java master course, java, master, course, dsa, time, complexity
Related Java Master Course Topics
Continue learning this concept
DSA in JavaDynamic Programming in JavaComplete guide to Dynamic Programming in Java covering memoization, tabulation, classical DP problems (Fibonacci, Knapsack, LCS, LIS, Coin Change), time/space optimization, and interview patterns.DSA in JavaGraph Data Structure in JavaComplete guide to graphs — representation, BFS, DFS, shortest path algorithms, topological sort, and classic graph problems in Java.DSA in JavaHashing in JavaComplete guide to hashing — hash functions, collision resolution, HashMap internals, custom hashCode/equals, and applications of hashing in problem-solving.DSA in JavaHeap (DSA)Complete guide to Heap data structure in Java covering Min Heap, Max Heap, heap operations, heapify algorithm, PriorityQueue class, heap sort, and applications with detailed implementations.DSA in JavaLinked List in JavaComplete guide to Linked Lists — Singly, Doubly, and Circular linked lists with Java implementations, operations, and classic interview problems.DSA in JavaQueue in JavaComplete guide to Queue data structure — FIFO principle, circular queue, priority queue, deque, BFS applications, and classic problems.