Challenge: Big-O Algorithm Time

Quick Index

Overview
Part 1: Big-O For Instance Methods
Part 2: Report
Examples
Provided Files
How to Submit
References

This challenge is about doing Big-O algorithm time complexity analysis on a LinkedList.

Linked list algorithms are described in detail here....

Big-O time complexity is described here...

This challenge is similar to the Big-O challenge we did for dynamic arrays.

On this page, "BigO analysis" or "Big-O" will indicate "BigO time complexity analysis".

Part 1: Big-O For Instance Methods

This part of the challenge is about doing Big-O a LinkedList's instance methods.

A Java file has been provided for you (see below). You will need to update the file with your Big-O answers.

The file contains detailed notes on steps.

Work To Do:

Unpack the "answers" package directory in the provided ZIP file
Open "LinkedListBigOAnswers.java"
For each method in this provided file, estimate O(1) or O(n) using Big-O for a linked list (see file for detailed notes)
If you are not sure of any answers, leave as-is (or make your best guess)

Part 2: Report

In the "answers" working directory, create text file named LinkedListBigOSummary.txt (named exactly like this to help grader).

Add the following to the file (based on your Big-O analysis on linked list):

Add label "Poorer Performers" and list two instance methods that are the poorer performers
Add label "Better Performers" and list two instance methods that are the better performers

Example report:

Poorer Performers
	methodName1
	methodName2

Better Performers
	methodName3
	methodName4

Where "methodName1", .., "methodName4" are replaced with actual instance method names that you analyzed in Part 1 (e.g. "first", "addLast", "removeFirst", "removeIndex", etc).

Examples

See the similar Big-O challenge in the DynamicArray chapter for step-by-step examples. Except that this analysis is based on linked list.

Provided Files

Download the provided files here...

How to Submit

Instructions:

Make sure your two solution files ("LinkedListBigOSummary.txt" and "LinkedListBigOAnswers.java") are in your "answers" directory.
Please assure the .txt file is named exactly as shown to make things easier for the grader
Create an archive ZIP file (".zip" extension)
Name the ZIP file in the usual way
Copy your "answers" directory into the ZIP
Make sure any source code file(s) compile before submitting (e.g. ".java", ".js", etc files)
Submit into D2L

References

Data Structures And Algorithms (DSA) (Chapter 403 - Big-O Complexity Analysis for a Linked List)

Chapter 403 - Big-O Complexity Analysis for a Linked List Challenge: Big-O Algorithm Time Complexity Analysis of Linked List

Contents Intro Challenge Two Challenges

Chapter Top Search TOC