Using your JSFiddle account and Javascript you will create a program that will i
ID: 3666051 • Letter: U
Question
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.
Explanation / Answer
JavaScript:
//create a program that will instantiate an integer array of size 1000
var array = new Array(1000); //O(1) constant
//when 'Update Array' is clicked call myFormSubmit function
document.getElementById("click").onclick = function() {myFormSubmit()}; //O(1)
//form function called and stores form input as variables
function myFormSubmit() { //O(1)
var index_entered = document.getElementById("index").value; //O(1)
var number_entered = document.getElementById("number").value; //O(1)
document.getElementById('updated-array').innerHTML = InsertIntoArray(array, index_entered, number_entered); //O(1)
}
function InsertIntoArray(array, index, number) { //O(1)
//Fill each array element with a random integer between 1 and 100.
//add a number between 1 and 100 to each element in array
// 100 gives random inclusive of 0..99
// +1 makes inclusive of 100
for(var a=0; a<array.length;a++){ // O(N) //do multiple times // 2002
//array[a] = a;
array[a] = Math.floor((Math.random() * 100) + 1); // O(1) //1000
}
//remove last element from array
//array.pop(); // O(n)
//alternate with splice (index, how many) index-1 is last index
//array.splice(-1,1); // O(n)
//alternate using array.length
array.length = array.length -1; // O(1)
//replace element (index, how many items to remove starting at index, values to add)
array.splice(index, 0, number); // O(n)
//accept user input as number
array[index] = number; // O(1)
//printing output
var updated_array = "";
for (i = 0; i < array.length; i++) { // O(N) //2002
updated_array += array[i] + " = Value of array index " + i + "<br>"; // O(1) //1000
}
return document.getElementById('updated-array').innerHTML = updated_array; // O(1)
}
function SearchArray(array, find) { // O(1)
for(var a=0; a<array.length;a++){ // O(N) //2002
array[a] = Math.floor((Math.random() * 100) + 1); // O(1)
}
a = array.indexOf(find); // O(n)
return a != -1 ? "Searched for " + find + " and found it at index: " + a : find + " Not found"; // O(1)
}
document.getElementById('find').innerHTML = "A2 "+SearchArray(array, 50) +". Time Complexity: O(1) + O(1) + O(1) + O(n) + O(n). Total number of operations on search array: 4007";
//OPTION
/*
function SearchArray2(array, find) {
for(var a=0; a<array.length;a++){ // O(N)
array[a] = Math.floor((Math.random() * 100) + 1); // O(1)
}
for (var i=0; i < array.length; i++) {
if (array[i] == find) {
return ("Searched for " + find + " and found it at index: " + i);
}
}
return (find + " Not found");
}
document.getElementById('find-option').innerHTML = SearchArray2(array, 50);
*/
// Count the number of operations performed on the array and output this to the screen.
document.getElementById('operations1').innerHTML = "A1 Number of Operations: 7018";
// Time Complexity using Big O Notation
document.getElementById('operations2').innerHTML = "A1 Big O Notation Time Complexity: O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(n) + O(n) justifies to: O(n)";
/*
Part 1 of 2 of Submission 2
Module1 Assignment 1 and 2
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.
For assignments 1 and 2 your Big-O notation and justification will be written in the html section of JSFiddle.
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. Count the number of operations performed on the array and output this to the screen.
Experiment with different sized arrays and inserting into a different index in the array. State using Big O Notation your time complexity and be prepared to justify your answer.
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.
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. Output the total number of operations. State using Big O Notation your time complexity and be prepared to justify your answer.
*/
Html:
<div id="operations1"></div><br>
<div id="operations2"></div><br>
<div id="find"></div><br>
<div id="find-option"></div><br>
<div id="form-array">
<form>
Index:<br>
<input type="text" name="index" id="index" value="3"><br>
Number:<br>
<input type="text" name="number" id="number" value="0"><br><br>
</form>
<input type="submit" id="click" value="Update Array"><br><br>
</div>
<div id="updated-array"></div>
CSS :
#click {
font-size: inherit;
color: #FFF;
background-color: #000;
width: 10em;
height: 3em;
}
A1 Number of Operations: 7018
A1 Big O Notation Time Complexity: O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(1) + O(n) + O(n) justifies to: O(n)
A2 Searched for 50 and found it at index: 21. Time Complexity: O(1) + O(1) + O(1) + O(n) + O(n). Total number of operations on search array: 4007
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.