Assignment 2 – Time Complexity
Objectives
1. Learn the concept of complexity and Big-O Notation
2. Analyze algorithms to determine the time complexity
3. Code simple algorithms and evaluate their complexity
Supports: Outcome 4 – Analyze the performance of algorithms and data structures.
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.
Lectures
Complexity is covered in section 2.1 of the lectures, please get familiar with the lectures at – All Course Lectures –
Lecture 2.1 -Big-O Notation and Complexity (Brightcove | Youtube ). In addition, you will need to get started with using lists and arrays, which are covered in Lecture 2.2 (Lists and Arrays).
There are some very good lectures out there that go into more depth and different aspects of time complexity;
Additional: Time complexity of a computer program (Youtube)
Assignment 2 Frequently Asked Questions – Do you have questions? Is your code not working? Check the FAQ to see if you made one of these common mistakes.
Assignment
For assignments 1 and 2, your Big-O notation and justification will be written in the HTML section of JSFiddle. Lecture – Inserting Data into an Array covers some useful information on the basic Javascript needed for this assignment. You will be using the Javascript array
Programming Assignment Part 1 –
Using your JSFiddle account and JavaScript, you will create a program that will instantiate an integer array of a specified size. This means you must create a text box interface and a button “Create Array”. Put a default value of 100 in the Text Box. When the user clicks “Create Array” create an array and fill each array element with a random integer between 1 and 100. You will need to research the random function to do this (the JavaScript function is Math.random()). This array should be a global variable.
You will next need an interface (same JSFiddle) with a second and third Text Box and button. The button will say “Insert into Array”. It will trigger a function that will read a number from the second Text Box and insert it into the array at the index of the third Text Box. This will be done by calling a function as specified below.
The name of the function will be InsertIntoArray and it will have 3 arguments (function InsertIntoArray(array, index, value)). 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. 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;
2. Create a loop to assign each array element a random value.
3. Do not use push or splice commands – assign elements by writing the code to perform all operations
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 (every time you use an = or == operator).
6. Output the count.
Programming Assignment Part 2 – Using the same JSFiddle, we will add one more button and Text Box. The button will be “Search”. Clicking the button will search the array and output the first index where the value entered in the Text Box is found. This will be done by calling a function SearchArray (function SearchArray(array, value)).
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 two numbers you must count it as an operation (only count comparisons). Output the total number of operations to find the first occurrence of the number searched or value not found. State using Big O Notation your time complexity and be prepared to justify your answer. This should be output in your actual JSFiddle.
Remember: You also need to put in the time complexity. This is NOT HARD – This is not a trick question; you will give a simple Big O notation of the time complexity of the search and the insertion on your HTML page. ( example
Complexity: O ___
Information:
There should be 4 TextBoxes – I recommend naming them (id = “name”) tbArraySize, tbInsertValue, tbInsertIndex, tbSearchValue. You can use your own naming scheme – but it is important you have a naming scheme. You will have three buttons; “Create Array”, “Insert Into Array”, “Search Array” I recommend naming them btnCreate, btnInsert, and btnSearch.
Sample Input
| Enter Array Size: |
| Enter Location: Enter Value to Insert: |
| Enter Value to Find: |
Sample Output
| Array output (100 items): 11,64,39,97,69,28,94,49,31,45,9,29,65,53,31,58,100,81,79,24,99,27,39,58,35,39,10,24,98,26,84,70,42,93,17,69,69,17,12,4,21, 75,86,25,82,32,69,21,42,24,42,100,61,25,97,60,12,100,40,40,10,75,78,86,25,3,11,65,44,17,35,4,78,77,53,5,53,18,19,26,31,51, 6,68,58,49,54,27,58,6,98,51,79,21,32,38,34,35,83,70 Value 99 inserted at location 20 – there were 80 operations performed in this insertion The time complexity of this algorithm is – (use big O notation) Value 99 was found at location 20 – there were 20 comparison operations performed in this search The time complexity of this algorithm is – (use Big O Notation) |
The HTML code to create the form is (you can use this)
<table style="width: 850px; height: 154px;" border="0"> <tbody> <tr> <td>Enter Array Size:<input style="width: 50px;" type="textbox" value="100" />
<input type="button" value="Create Array" onclick="CreateArray()"/></td> </tr> <tr> <td>Enter Location: <input style="width: 50px;" type="textbox" value="5" /> Enter Value to Insert:
<input style="width: 50px;" type="textbox" value="99" />
<input type="button" value="Insert Into Array" onclick="InsertIntoArray()"/></td> </tr> <tr> <td>Enter Value to Find: <input style="width: 50px;" type="textbox" value="20" />
<input type="button" value="Search Array" onclick="SearchArray()" /></td> </tr> </tbody></table><br/><div id="output">The array output will go here</div>
Submission Instructions
You will submit a link to your code in JSFiddle. The link can be submitted as a text file, I recommend you submit the link as a simple link in the Drop Box. The code above can go into the JSFIddle HTML window.
Assignments Grading Criteria
For both programming assignments, Javascript code that uses the push or splice commands will not be accepted. You must hand code both assignments using only primitive operations (+ , = ). If you have questions about what operations are legal, post your questions to the bulletin board.
More Information
There are some wonderful resources out there to help you get better at algorithms and complexity. I am listing some of them here; most were submitted by students on the class discussion boards.
This little article covers the concept of Big-O notation in nice English terms. You should know and understand everything in this article – https://dev.to/sarah_chima/the-big-o-notation-an-introduction-34f7
MIT Intro to Computer Science Lecture 8 – https://www.youtube.com/watch?v=ewd7Lf2dr5Q&feature=youtu.be – Covers complexity in great depth.
MIT Introduction to Algorithms Lecture 23 – https://www.youtube.com/watch?v=moPtwq_cVH8 – Looking at the polynomial completeness