Time complexity is a useful concept in programming. It’s essential for job interviews, but beyond that to really be a good programmer you need to know how cumbersome your algorithm is going to be. For 10 items, something that takes 2 seconds per item is only 20 seconds, but what if you have a million items?

In general, time complexity is measured by how long it takes a number of items (n) to be processed. It is the relationship between the number of things you have to do and the work to be done. Something that takes the same amount of time no matter have much of it you have to do, would be constant time. If I had 10 items or 1 million it would only take me 2 seconds to process. On another extreme is something called the handshake problem. If you only have two people in a room they only have to shake one another’s hands (one handshake). If you have 10 people, they each shake 9 other hands (55 handshakes total, we’ll get to the math in a moment). This is quadratic time.

Here’s a visual of the common programming time complexities:

Lets start with constant time again. In programming, constant time is like deciding whether a number is even or odd:

1

n % 2 = ?

This is just one expression. You run and you’re done. It’s always going to take a certain amount of time, no matter what n you give it. In big O notation we would write this as O(1).

Next, my favorite, as far as understanding goes. Linear time. In programming, linear time, is like running through a loop of n numbers and doing something.

1
2
3

for( var i = 0; i < n; i++ ){
   do something..
 }

The more things (‘n’s) you have, the longer the algorithm is going to take. It’s a 1:1 ratio. If 1 thing takes 1 second, 2 things are going to take 2 seconds. This is O(n).

Quadratic time is worse than linear time. It’s like the handshake problem or in programming terms a for loop within a for loop. For each n we need to run through all the numbers 1 through n.

1
2
3
4
5

for( var i = 0; i < n; i++ ){
   for( var j = 0; j < n; j++ ){
     do something..
   }
 }

Each n thing is done n times. This is n * n or in big O terms O(n²).

Logarithmic time is all kinds of magic. It tapers off to a near constant for larger ‘n’s. This is possible because of the magic of halves. In a binary search tree there are only two options to descend, left (options lower than the current value) or right (options higher than the current value). Either choice will cut off roughly half of all the possible values. On the next level, you have the same choice, either you’ve found your value, or you go left or right, halving your options again.

1
2
3
4
5
6
7
8

while ( low <= high ) {
   var mid = ( low + high ) / 2;
   if ( target < list[mid] ){
     var high = mid - 1;
   } else if ( target > list[mid] ){
     var low = mid + 1;
   } else { break; }
 }

If you’re constantly halving the amount of things you have to check, eventually you hit a roughly constant time for an n search. This is O(log n).

This post has been brought to you by a forum post on time complexity, bits and pieces of the wiki article on time complexity, and this inspirational code class ad featuring my lead instructor from his Twitter days.

2nd interview with HackReactor today! This time it was an actual tech interview so I was even more nervous. Once again my interviewer was a pleasure to talk to and very calming. I also picked up my new favorite phrase: “You nailed it with a nail gun.” This was in regards to one of the functions I had to implement. It’s crazy how different my experiences with interviewing for two different schools where. AppAcademy just was not warm and fuzzy at all which I guess is OK, but they just never seemed to care who I was, just what I could do with code. I did OK (got a conditional acceptance pending a final interview) but I felt like they put so much emphasis on logic puzzles, which, heck, shouldn’t they be helping me with in prep to get me a job? I’m also not sure how I feel about the lack of finding out whether I’m some crazy mouth-breather who can’t even interact with people. I just wonder what types of people end up in the class.

HR on the other hand has been surprisingly FUN to interview with. It hasn’t been exactly easy, but it has been fun to play with JavaScript. The first interview was nice and lite and I got to show off that I knew what recursion was (but forgot to add a base case initially - d’oh). Then the take home work was well designed and pushed me along to learn some jQuery and how to pull data using AJAX. Then the last tech interview had me creating my own versions of some Underscore.js functions which was fun and thought-provoking and definitely tricky but not in a gotcha sort of way but more of a pushing me in the right direction to learn it myself. If this is what the class feels like, sign me up!! HR just seems so nurturing and I love to learn.

I should know if I got in (or if I have to try again, because goddamnit I’m trying again if I don’t make it this time) by Friday. Keep your fingers and toes and eyes crossed for me!

I had my first interview with Hack Reactor today. That was awesome. It was a 180 from my two App Academy interviews. Doug from HackR was amazing. First of all, he was on time! I figured that was a good omen. But then he was also funny and sweet even though my Skype was being funky initially. I felt very at ease by the time the initial coding assessment came around. It was actually kinda fun and straightforward and he told me I’d moved on to the take home and technical interview! We scheduled it on the spot and I took the first opening available (next Tuesday). We then chatted a bit more (I learned that they take about 30 students now and had 5 women the last go round).

Basically I’m just really, really excited and beyond glad I decided to focus on just this program. I think it is exactly what I’m looking for.