Module 1 - Time Complexity

Summary

Time complexity is measured using a notation known as Big-O notation. This is covered in depth at http://en.wikipedia.org/wiki/Big_O_notation and also within the textbook. In Big O analysis you must determine the complexity of an algorithm and determine how it performs as the sample size of the data it performs an operation on increases towards infinity. If you need a little more on this the following video should be helpful;

Topic

Time Complexity is covered in Topic - Introduction to Data Structures you should go through and make sure you understand the notation associated with complexity that are covered in this topic. You will be able to determine how well you understand the notation as you work your way through the quiz.

Assignments

For assignments 1 and 2 your Big-O notation and justification will be written in the html section of JSFiddle. Lecture - Javascript Basics - Inserting into an Array covers some useful information on the basic Javascript needed for this assignment.

Program Assignment 1 - Using your JSFiddle account and JavaScript you will create a program that will instantiate an integer array of size 1000. Fill each array element with a random integer between 1 and 100. You will need to research the random function to do this.

You will write a function with 3 arguments. The name of the function will be InsertIntoArray. Argument 1 is the array, argument 2 is the index of where you are going to insert a new number, argument 3 is the number to insert. The program should insert the new number at the index given and shift all the previous entries index up by 1. Since the array is capped at 1000, the highest element of the array will be deleted. Count the number of operations performed on the array and output this to the screen. An operation is if you assign a value or compare a value - only compare or assign operations should be counted.

Change the array size to 100 and insert into a different index in the array. State using Big O Notation your time complexity and be prepared to justify your answer.

Programming parameters:

1. Create the array in Javascript: var array = new Array(1000);

2. Create a loop to assign each array element a random value.

3. Do not use push or splice commands - assign elements by using = (in code)

4. When inserting you will be pushing the last value off the end of the array (everything shifts right)

5. Use a global counter to count every time you make an assignment (use an = or == operator)

Program Assignment 2 - Using your JSFiddle account and Javascript you will create a program that will instantiate an integer array of size 1000. Fill each array element with a random integer between 1 and 100. You will need to research the random function to do this. Do NOT sort the array. You can use the same code as Part 1 to create the array. In fact you can achieve both Assignment 1 and Assignment 2 with a single program.

You will write a function with 2 arguments. The name of the function will be SearchArray. Argument 1 is the array, argument 2 is the value you are searching for within the array. Each time the program compares 2 numbers you must count it as an operation (only count comparisons). Output the total number of operations. State using Big O Notation your time complexity and be prepared to justify your answer. This should be output in your actual JSFiddle

Quizzes (Quiz Submission Instructions )

Quiz 1 - Complete Analysis of Algorithms quiz at http://geeksquiz.com/algorithms/analysis-of-algorithms/ 

Make sure you get a screen capture of the final grade. If you have questions on one of the questions - remember, you will be required later to know this stuff, please post to the bulletin board. Also look through the discussions that accompany the questions on the site - some are quite good.

Assignments Grading Criteria

For both programming assignments, Javascript code that uses the push or splice commands will not be accepted. You must hand code the both assignments using only primitive operations (+ , = ). If you have questions about what operations are legal post your questions to the bulletin board. You must complete both programming assignments and  the quiz to receive credit. The quiz is worth 2/10, each program is worth 4/10 and must be fully functional for credit.

Navigation

Previous: Module 0 - Getting Started 

Next: Module 2 - Algorithms

List of All COP3530 Modules