# Maker Square Day 4

Video Lecture on Complexity Analysis. Space = memory. Time = when. How does time grow?

An algorithm is a plan that helps you solve problems.

To compare all numbers is n^2 is of quadratic time complexity.

Find largest by finding smallest? On

if sorted list, compare first and last is constant time. Gives an approximation of time, not an actual number. Note, highest order first. Think about it as LARGE(n).

Static analysis = analyse and reason through it with graphing.

Constant = array look up
O(log n) = binary search
linear O(n) = print array;
O(n^2) = find largest (nested for loops)
O(c^n) = guess password of (n) length

Binary Search?

``````var binarySearch = function(array, ele, start, end){
var start = start || 0;
var end = end || array.length-1;
var midpoint = Math.floor((end + start) / 2);
if (array[midpoint] > ele){
return binarySearch(array, ele, start, midpoint-1);
}
else {
return binarySearch(array, ele, midpoint+1, end);
}
}``````

Protoypal Classes

Q: Can you think of a way to use prototype chains that might help? Removes extend loops, allows chaining of values and having them push out.

Talking about obj within constructor class is the same as talking about every instance. To create a function for making instances is a line in that function where you create a new instance object (object.create(car.methods)) an object as a prototype and some logic for augmenting the new object with properties that make it unique from other objects in the same class (obj.loc = loc).

Pseudo-classical Classes

new keyword = when new is used before a function it acts in a special mode called constructor mode. (var foo = func() {blah;}; var blah = new foo;) constructor mode sneaks in the this.object.create(car.prototype); and the return this; at the end of the function. Pseudo-class has two parts, the prototype properties to hold similarities  and the constructor function to hold the differences.

Open Source Lecture

Productivity Tip: Look at OctoTree for chrome and git access

To contribute to open source projects is a good thing! You don’t have to be a genius to help out. Look at the larger repos. Think about clarifying comments, adding tests, even making sure the style is consistent. These things are needed and appreciated.

Tips for success. Follow repo styles and conventions. Pay close attention to the commit message conventions. Changes should be a single commit. Well written merge comments will increase the chance of a successful pull request.

Data Structures

Quick review on scope and closure. Scope = set of rules to define value availability lexical scoping. Closure = if you instantiate an object the instantiated object has access to the original object.

Hash Tables

Very similar to an object. 2 components to a Hash table. The storage part and the hashing function.  The hashing function takes a key, and dresses it up so that its always the same dress for the same key. This hashed key equals the location in storage. We must watch for collisions, and distribute as evenly as possible to reduce collisions.