Time Complexity of Algorithms

While writing out algorithms in code, a programmer must be aware of their drain on the performance that may be passed onto the user experience or aware of the potential drain of CPU usage. A friend recently told me of an infinite (but harmless) loop that the code for their database had and the “damage” was an additional $100k in CPU usage for that machine for the month (because the server was hosted and paid by CPU usage).

Constant Time – O(1)

Increasing the problem size does not change the number of operations.

Examples:

  • Pulling from the top of a stack or from the front of an array. No matter how large the stack or array is, the steps to complete the operations is one.
  • Looking up a value on an object when the key is known.

Linear Time – O(n)

The number of operations is proportional to problem size. The larger the list the longer the operation will take to complete by that n number.

Examples:

  • Finding a single item in an unsorted array
  • Searching for a single value in a linked list
  • ForEach
  • Slice and indexOf is linear in Javascript

Logarithmic Time – O(log c n)

Multiplying the problem size by constant adds the same number operations. How many times do I have to divide n by c to get to 1?

Examples:

  • Dividing is almost always log.
  • Finding an item in a sorted array using a binary search tree.
  • Finding a name in the phone book, open up half the book then determine if you have to check the first half or the second, then go to halfway between that half of the book, repeat.

Quadratic Time – O(n*n or n2)

The number of operations is proportional to the square of the problem size.

Examples:

  • Two nested for loops, usually
  • Any operation that multiplies two numbers by each other
  • Comparing two items as in a bubble sort or quick sort

Exponential Time – (Ocn)

The number of operations is proportional to some constant raised to the power of problem size. Any operation that would double the number of inputs. If the number of input grows, the time to complete the operation grows exponentially.

 

Determining Complexity

  1. Determine what variable(s) represent problem size (this is n)
  2. Write the number of operations in terms of n
    1. lines of code in series are added
    2. lines of code nested in other function calls or loops are multiplied
  3. Find leading term and drop coefficients (instead of 5n*n, then it’s n*n)
  4. If adding operations, choose the worst case (linear trumps constant, linear trumps logn, etc) and this is the overall time complexity.
  5. If multiplying, the time complexity is the product of both (n*logn = nlogn)
Advertisements

D3 Data Driven Documents

D3 is a JavaScript library which gives power to your front end by providing data to create and delete elements on the page, along with simple updating of that data and other elements on the page. The typical patterns for D3 are enter(), update and exit().remove() and a brief example of each is below.

To get started, you will have to find the element or class you want to do work on. If you are familiar with jQuery, then this should look similar (it’s similar to find()). You can start with the top element and dive into each child to find the one you want. Then you choose .select() or .selectAll(). If you are looking for a single element or the first element with that name use .select(), if you are looking for all the elements with that name use .selectAll(). If you look for a class instead of an element be sure to use the dot, .selectAll(“.trumpet”) or use a hash for IDs, .selectAll(‘#trumpet’).

Example:

// Initialize the page, join the data, then set a reference variable so there is less to type later.
var heightValues = [30,40,50];
var myPage = d3.select('body')
.data(heightValues, function(d) {return d;})

// ENTER() Since we have more data than elements on the DOM, we call .enter() and it adds div elements with a specified height from the data above to the DOM tree.
myPage.enter().append('div').attr('height', height)

// UPDATE Let’s update our height with random numbers now. No special function is needed for updating. Find the element or class using .select() or .selectAll() and then reassign the value of the .attr()
myPage.selectAll('div').attr('height', function(d) { return Math.random(); })

// Now if we wanted to delete an element we can remove an item from the data array
heightValues = [30,40];

// REMOVE() Then call .exit() with a .remove() and the element or class without data (the last div element) will be removed from the DOM. If we only called .exit(), the element would be left in the DOM with no data value.
myPage.exit().remove();

 

Building a REST API

Navigate to the repo location in terminal:

cd AutomationDatatools/distillery/

Start the server

DEBUG=distillery ./bin/www

Go to your web browser and navigate to the localhost

http://localhost:3000/api/imsreports

The structure looks like this for public, routes and views:

|– public
|   `– stylesheets
|       `– style.css
|– routes
|   |– api
|   |   |– imsreports.js
|   |   `– index.js
|   `– index.js
`– views
|– api
|   `– index.ejs
|– error.ejs
|– index.ejs
`– main.ejs

Code School Part 3 Exercise 1.13

This one stumped me for a bit. In scrum a fellow teammate said he’d offer some suggestions if I sent him my code.

This was my code prior to suggestions from teammate:

var applyAndEmpty = function(input, queue){
var amount = queue.length;
for (var i=0;i<amount.length;i++){
input = queue(input);
var removeFirst = queue.shift();
}
};

return applyAndEmpty(start, puzzlers);

This is my final code that worked in the exercise:

var puzzlers = [
function(a) { return 8 * a – 10; },
function(a) { return (a – 3) * (a – 3) * (a – 3); },
function(a) { return a * a + 4; },
function(a) { return a % 5; }
];
var start = 2;
var applyAndEmpty = function(input, queue){
var amount = queue.length;
for (var i=0;i<amount;i++){
input = queue.shift()(input);
}
return input;
};
alert(applyAndEmpty(start, puzzlers));

My teammate pointed out that I was calling .length twice. With the below statement, I was so close! They were not the right syntax and I was writing more complex statements than they had to be.

input = queue(input);
var removeFirst = queue.shift();

My code also had the applyAndEmpty as a return statement and it should have been an alert statement.

Puzzle Exercise Instructions

Now the people at Poplar Puzzles would like you to treat an array of functions like a Queue, passing the result of each function into the next until the Queue is empty. They’ve sent you the puzzlers Queue of functions, and the following instructions:

In a variable called applyAndEmpty, build and store a function that takes in an input number and a Queue of functions as parameters. Using a for loop, apply the Queue’s functions in order to the input number, where the results of each function become the next function’s input. Additionally, the Queue should be empty after the function is called. – PuZzLe MaSTeRs

Lastly, call the applyAndEmpty function using the provided start variable and the puzzlers Queue as arguments, and alert the result.

Error Message with incorrect code

Incorrect Submission: Make sure that you declare the applyAndEmpty variable properly.

 

More of my CodeSchool JavaScript Road Trip journey can be found on GitHub.

Code School JavaScript Road Trip Part 3

For a new project, I’m taking the Code School JavaScript trainings and I’m finding the stories and the problems to solve quite enjoyable as compared to Code Academy. It was smooth sailing until Road Trip Part 3, where my velocity slowed due to the complexity of the problem statements. I’ve realized that there are many ways to solve the problem and the way I’d solve them is not the point of the lesson, which is good because it’s teaching me new ways of looking at a problem.

My code, and thoughts on solving problems with CodeSchool Javascript Road Trip is logged in GitHub.

 

Web Development Project (Continued)

Continuation of Web Development Project post.

The Perl script was created to post to the PHP page. I created and it enters the data into the MySQL database beautifully. BTW – a better DB GUI/query tool: Sequel Pro.

Next project my friend requested was a graph of the data. I used Google Charts, and added a drop down which pulls IP addresses from the database.
Google Chart Select IP

[Figure 1 – Drop down pulling IP addresses from DB]

Once you chose the IP address, it passes the IP address via Ajax to another page, which processes it and then sends a response back and then displays the graph and a data table for that IP.
Google Charts

[Figure 2 – Google Charts, dynamically pulling from DB]

After using Google Charts to create an initial page (quick and dirty), I moved onto using Google’s Annotated Time Line (Visualization API) for the next set of graphs. Google Annotated Time Line will allow for zooming into the data and a more dynamic feel to the graph as opposed to the static Google Charts graph above.

The project grew and it was necessary to pull from multiple MySQL databases and tables, including a wordpress database which is populated with data via email. Realized it was necessary to add 15 hours (so time matches up with China time) so our wordpress posts matched our data. I looked into how to do it with PHP – maybe pulling the whole date from the DB and then doing work on it in PHP, but thought there has to be a simpler way, and ended up using DATE_FORMAT and DATE_ADD in the SQL statement to pull correct time. I love SQL.

The purpose of this graph is to create a visual representation of what has been said in emails, in the office and to the higher ups for the past weeks/month. It will show, on into the future, the health of the project my friend is a part of and if the problem is getting better or worse. Unfortunately over the days we worked on this, the graph continued to show that the project was not going well. My friend will have a lot on his hands when he goes into the next meeting, but now perhaps they will see the seriousness of the problem he’s trying to illustrate.

Annotated Time Line Version 1

[Figure 3 – Graph from version 1 code with test data]

Turns out my friend and I made a great team. I set up the database and page framework for the graphs, then we worked hand in hand to display the information necessary. Then he did some pretty sexy design enhancements to make the graphs easier to read at a quick glance, which is what most managers and CXO’s desire.

Annotated Time Line Version 2
[Figure 4 – Graph from version 2 code with test data]

Code can be found here: https://github.com/kathy-ems/iosdevicedashboard

Web Development Project

Note: This was installed on Mac OS X 10.5 (Leopard)

The other night was discussing with a friend one of his processes at work, which was very manual, and trying to find ways to automate it. A few times I said, “a few SQL queries would probably help out”. Somehow (though I didn’t resist) I was assigned the task of creating a MySQL database and a website to assist with this project.

First step was to get MySQL installed on my Mac. I chose to do a manual install verses the MySQL dmg package. I had to track down the mysql-5.1.33.tar.gz file because the file that downloaded was only 4KB. In addition, I learned how to view ‘hidden’ files on a Mac – TextWrangler simplified it for me.

The directions went smoothly after finding the initial tar and hidden files… up until I hit the “A Note about Security” section. I couldn’t find the my.cnf file. In my search for this my.cnf file I came across a site that described how to open up Apache for PHP use and I figured it’d come in handy.

I decided to worry about the security step later (and a later step created the my.cnf for me). Next step was to get a gui interface so I could create a database, create a table and load it up with data. I downloaded and installed the MySQL GUI Tools. As a previous Windows only user, MySQL Administrator was unfamiliar at first, but I quickly found the table structure and made my rows within a table I called “products”.

I now had my table, so I switched over to the MySQL Query Browser. After some changes to get an auto-incrementing primary key, and to change the date field into a time-stamp field, I inserted data into my table using SQL scripts.

INSERT INTO products
(serialNum, errorCode, data) VALUES(‘123456’, ‘Some Error number 1′, ’09/01/2009’ )

INSERT INTO products (serialNum, errorCode) VALUES(‘123456’, ‘Some Error number 1’ )

Next step was to display these data points into a web browser. I enabled Apache on Leopard via System Preferences -> Sharing ->Web Sharing. Placed a simple .html into the user–>Sites folder, visited http://localhost/username/ and bang, an error. “Can’t find the server”. So, I moved the username.conf file to the proper location for Apache2 to try to resolve the issue. No luck (but I have a feeling it one less problem in the future). Finally checked the console’s error messages and the solution was to create a folder for the log files.

Success! The simple html page displayed as beautifully as “Hello World” can. An IT professional’s favorite words. I redirected to the DisplayData.php page, which I had already created using SQL queries to retrieve all the data and display it in a simple html table. Then with a little tweaking of the table structure to make it look just the way wanted, I was ready for the next step.

Obtain specific requirements of the page/task:

  • Can you get a php page that takes in variables posted to it? – A Perl script pass variables to the php page
  • and populate the db with the info?
  • date = X – (is this a timestamp date or a date entered by the user? Perl script.)
  • IP = X– (This will need to be a varchar(15)
  • Data in coma sep. values = key, value, key, value (explode is a possibility) – a “key” is a column heading. Need to find out how to automatically/dynamically add columns to tables when the column doesn’t pre-exist.
  • need to match keys (column headings) and overwrite if the date is the same
Had problems with reloading the process.php page. It would add another record to the database. Finally used header and GET to redirect to a different php page and pass the info for displaying on the final page.