Big-O Notation

Assignment 2

by Jake Jernigan

HTML

Index:
<input type="textbox" id="index" />
<br/> Value:
<input type="textbox" id="value" />
<br/>
<input type="button" value="Insert into Array" onClick="insertIntoArray();" />
<br/> Search:
<input type="textbox" id="search" />
<br/>
<input type="button" value="Search Array" onClick="searchArray();" />


<div id="output">
</div>

JavaScript

var array = new Array(1000);
var d = "";
var count = 0;
var count2 = 0;
var found = 0;

for (var i = 0; i < array.length; i++) {
  array[i] = Math.floor(Math.random() * 100 + 1)
}

function showArray() {
  for (var i = 0; i < array.length - 1; i++) {
    d += i + ' : ' + array[i] + "<br/>";
  }
  document.getElementById("output").innerHTML = "Insertion Operation Count : " + count + "<br/>" + "Comparison Operation Count : " + count2 + "<br/>" + d;
}

function hideArray() {
  d = "";
  document.getElementById("output").innerHTML = " ";
}

showArray();

// Big O notation for this function is O(n). The number of operations that occurs is directly increased by n

function insertIntoArray() {
  hideArray();
  var index = parseInt(document.getElementById('index').value);
  var value = parseInt(document.getElementById('value').value);
  d = 'Inserting ' + value + ' at index : ' + index + '<br/>';

  for (var i = array.length - 1; i > index; i--) {
    count++;
    array[i] = array[i - 1];
  }
  array[index] = value;
  count++;
  showArray();
}

// Big O for this function is O(n) Since it is a linear comparison of the entire array.

function searchArray() {
  var search = parseInt(document.getElementById("search").value);
  for (var i = 0; i < array.length; i++) {
    count2++;
    if (array[i] == search) {
      found++;
    }
  }
  d = found + ' Results found in array' + '<br/>';
  showArray();
}