Module 2: Big O
Module Overview
Understand time complexity analysis and Big O notation for algorithm efficiency.
Learning Objectives
- Explain what Big O notation measures
- Identify the Big O time complexity of common operations
- Compare the efficiency of different algorithm approaches
- Analyze your own code to determine its time complexity
- Optimize algorithms for better performance based on Big O analysis
Understanding Big O Notation
What is Big O?
Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it's used to classify algorithms according to how their run time or space requirements grow as the input size grows.
Common Big O Complexities
O(1) - Constant Time
The operation takes the same amount of time regardless of the size of the input.
// Example: Accessing an array element by index
int value = array[5]; // O(1)O(log n) - Logarithmic Time
The time complexity increases logarithmically as the input size grows. Common in algorithms that divide the problem in half each time.
// Example: Binary search
public int binarySearch(int[] array, int target) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (array[mid] == target) {
return mid;
}
if (array[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}O(n) - Linear Time
The time complexity grows linearly with the input size. Common in algorithms that process each element once.
// Example: Linear search
public int linearSearch(int[] array, int target) {
for (int i = 0; i < array.length; i++) {
if (array[i] == target) {
return i;
}
}
return -1;
}O(n log n) - Linearithmic Time
Common in efficient sorting algorithms like mergesort and quicksort.
// Example: Merge sort
public void mergeSort(int[] array, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
merge(array, left, mid, right);
}
}O(n²) - Quadratic Time
The time complexity grows quadratically with the input size. Common in algorithms with nested iterations.
// Example: Bubble sort
public void bubbleSort(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
// Swap array[j] and array[j + 1]
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}O(2^n) - Exponential Time
The time complexity doubles with each addition to the input size. Usually seen in recursive algorithms that solve a problem of size n by solving two subproblems of size n-1.
// Example: Recursive Fibonacci
public int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}Analyzing Your Code
When analyzing the time complexity of your code:
- Identify the basic operations that are counted
- Find the input size that affects the running time
- Determine how the operations grow relative to the input size
- Express this growth in Big O notation, focusing on the most significant term
Optimizing Based on Big O
Once you understand the time complexity of your algorithms, you can make informed decisions about optimization:
- Replace nested loops with more efficient algorithms when possible
- Use appropriate data structures (e.g., HashMap for O(1) lookups)
- Avoid unnecessary computations within loops
- Consider space-time tradeoffs to improve performance
Guided Projects
Mastery Task 4: Inevitable
Mastery Task Guidelines
Mastery Tasks are opportunities to test your knowledge and understanding through code. When a mastery task is shown in a module, it means that we've covered all the concepts that you need to complete that task. You will want to make sure you finish them by the end of the week to stay on track and complete the unit.
Each mastery task must pass 100% of the automated tests and code styling checks to pass each unit. Your code must be your own. If you have any questions, feel free to reach out for support.
Change is inevitable, according to famous British Prime Minister Benjamin DisraeliLinks to an external site., and the important question is how we carry it out. It's time to bring the big change to the Missing Promise CLI.
The service already has a flow to retrieve the Promise made to a customer at checkout by calling the DeliveryPromiseService. We know we can improve it by getting the Promise at the time of packaging from OrderFulfillmentService (OFS). Knowing that change is inevitable, we anticipate that more improvements will be required in the future: maybe promises from shipping companies, from drone dispatchers, from Prime Now, from Fresh... who knows?
Milestone 1
The current design only supports one client returning a promise. Redesign the PromiseDao to support multiple clients, including the OFS client we know about and future clients we can't anticipate right now.
Find the PromiseDaoDesignReview template to your src/resources. Answer each of the questions to help you better grasp how the code should change.
Milestone 2
Implement your OrderFulfillmentServiceClient class to get the packaging promise from the OrderFulfillmentService.
Create the new OrderFulfillmentServiceClient class, inside a new Java package, com.amazon.ata.deliveringonourpromise.orderfulfillmentservice, following the pattern of the other service clients.
Before you write unit tests for it, consider how error-prone code would be if every class that needed your client instantiated a new one -- especially if the client had a lot of configuration options. It would be much more robust to build a single, correct client when the program started, then provide that client to every class that needed it. This is known as "Dependency Injection", and it's similar to what our App class does.
Add a method in the App class to create your client. Write unit tests that get their OrderFulfillmentServiceClient by calling the App method, instead of calling a constructor directly.
You will find that Promise objects are populated using a bunch of concatenated with***(value) calls, followed by one build(). This is an application of the "Builder" pattern for constructing objects with many fields. Use the existing DeliveryPromiseServiceClient as a reference to implement the OFS client similarly.
Milestone 3
Update the PromiseDao to match your design and retrieve the packaging promise from your OrderFulfillmentServiceClient. It should also use the App class to get its clients, rather than instantiating them itself. Make sure the existing unit tests continue to pass.
Each of the following tests should be run separately and pass using the following commands - one command per test:
./gradlew -q clean :test
./gradlew -q clean IRT
./gradlew -q clean MasteryTaskFourTestsExit Checklist
- You created mastery-task4.txt in the src/resources folder of the project
- You implemented OrderFulfillmentServiceClient
- You updated the PromiseDao to retrieve the packaging promise from OFS
- Your Mastery Task 4 TCTs are passing locally
- You have pushed your code