Quick Index
Overview


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

DynamicArray algorithms are described in detail here....

Big-O time complexity is described here...

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 complexity analysis on DynamicArray's instance methods.

A Java file (DynamicArrayBigOAnswers.java) has been provided for you to put your answers (with some answers completed to help you get started. This file also contains detailed notes on steps.

Work To Do:


NOTE WELL -- Ignore 'grow' and 'shrink' in your analysis -- in other words, assume that any 'grow' or 'shrink' operations do not need to be performed for the purposes of your Big-O analysis.

Part 1 - Example


Pick Method to Analyze
  • Open the provided JAVA file
  • Find method "size_BigO"
  • This associates to the "size" method (name preceding the underscore "_").
public String size_BigO() {
		return "YOURANSWER";
}
Do Big-O Analysis
  • See the referenced "Introduction to Big-O" (and other refs) for guidance
  • Do Big-O analysis on your DynamicArray's "size" algorithm/method
  • Determine what the Big-O level (notation) is for the method "size"
public String size_BigO() {
		return "YOURANSWER";
}
Make Guess
Let us say, for the purposes of this example, that you determine that Big-O for your "size" algorithm/method is "O(1)".

You would then replace "YOURANSWER" with "1" (as shown).
	public String size_BigO()  {
		/* Your algorithm for "size" should produce logic that
		has a Big-O "O(1)" performance level. I.e. the algorithm
		work (effort) should be constant (unchanged) as structure size grows
		to a very large size. For "O(1)", we answer "1" as shown below
		in this method (completed for you) */
		return "1";
	}


Three Examples Provided
You will find three examples (completed) in the provided file -- "DynamicArrayBigOAnswers.java".


Part 2 - Report


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

Add the following to the file (based on your Big-O analysis of DynamicArray):


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).


Provided Files


Download the provided files here...

How to Submit


Instructions:


References




































Data Structures And Algorithms (DSA) (Chapter 306 - Big-O Complexity Analysis for a Dynamic Array)










Chapter 306 - Big-O Complexity Analysis for a Dynamic Array Challenge: Big-O Algorithm Time Complexity Analysis on a DynamicArray

Contents Intro Challenge

Chapter Top Search TOC