When math is useful

Determining Big O(n*n) is relatively straight forward when compared to other forms. Given,

start = 0;
end = n;
for (i = start; i < end; i++)
  for (j = start; j < end; j++)

It’s clear, for every iteration of the outer loop, the inner loop iterates n times. The outer loop iterates n times as well, so, total number of iterations are n*n. In Big O notation, the runtime complexity may be represented as O(n*n).

But, what about –

 start = 0;
 end = n;
 for (i = start; i < end; i++)
  for (j = i; j < end; j++)

Note: The inner loop starts iteration at i

The code above represents a very practical use case, for example, when finding indexOf, substring et al.

When determining the runtime complexity, intuition will suggest O(n*n), which, is correct. But, how do we arrive at that? Because at each iteration, i, of the outer loop, we are iterating n-i times in the inner loop. The number of inner loop iterations are decreasing with each iteration of the outer loop.

Let’s break it down by each iteration –


i = 0, inner loop iterations = n

i = 1, inner loop iterations = n - 1

i = 2, inner loop iterations = n - 2

i = 3, inner loop iterations = n - 3


i = n - 2, inner loop iterations = n = (n - 2) = 2

i = n - 1, inner loop iterations = n - (n - 1) = 1

Sum total of all iterations –

n + (n - 1) + (n - 2) + (n - 3) .... 2, 1

If we reversed the above, it will look like an arithmetic series of positive integers up to n.

1, 2 ... (n - 3) + (n - 2) + (n - 1) + n

Which, as we know is equivalent to –


The above expands to –

(n*n)/2 + (n/2)

In Big O notation (a notation of asymptotic analysis), we drop the lower terms, which, leaves us with –


Some thoughts on maintainable code

I take pleasure in writing good code – maintainable, industrial strength, and sometimes beautiful. Here are some of the considerations I make to achieve that goal.

But, first, why is maintainable code important? Maintainable code will generally live longer, be more bug resistant and scale to some degree. With ever increasing engineer attrition, it will result in shorter ramp up times for new hires.

Readability is the most important and biggest consideration. Readability starts with ‘naming’ method/function names, variables, constants etc meaningfully. It may seem like a quick and easy task, but, is usually quite the opposite. Names are important because they tell the story of the code. I believe, readable code requires minimal to no documentation. Similar to a good story, the challenge is in finding succinct and yet meaningful names.

Code uniformity starts with setting up code formatting rules (not guidelines, but, rules), such as, line indentation, spacing between language constructs such as (, {, etc and keywords. It is important to develop rules for where things will be found, such as, constants. Very minute details can make or break code uniformity. For example, in a java class, if ‘this’ is explicitly used to refer to an instance of a Java class, then, it should be done consistently throughout the class. Code uniformity directly affects code readability.

MODULARITY/DRY (Do not repeat yourself)
Functions/methods are the essence of programming languages. As a rule of thumb, if the same piece of code is used more than once, then, it should be written as a function. But, often times, it is also good practice to encapsulate code in a function even if the code is used once. It mostly boils down to readability. Any code reader using a laptop will appreciate if a block of code fits the size of their screen. There are other benefits too, such as, creating units of testable code.

Being clever with code is achieving a desired result with fewer (or least) lines of code. But, if clever code reduces or distorts readability, it is better to refrain from being clever. Clever code can leverage good, but, rarely used features of a programming language – can act as a purveyor of knowledge.

Performance should be the most important consideration if it is practically hindering/slowing the experience for the consumer of code or is the value proposition of a business. But, in most cases, the performance degradation that comes at the cost of code readability is negligible.

Writing a piece of code is like writing a short story in english. There are rules for writing in english, which, help ensure the writing is easy to understand and enjoyable. Well written sentences maintain tense, don’t introduce ambiguity, organize different thoughts in paragraphs etc. Maintainable code too, follows principles that help make it clear and easy to read and understand.

JavaScript – Primitive vs Reference Types

Two areas of confusion around JavaScript primitive vs reference types
1. If every thing in JavaScript is an object
2. Passed by value vs passed by reference

1. If every thing in JavaScript is an object

This is untrue since JavaScript clearly defines the following primitive types –
1. Number
2. Boolean
3. String
The confusion arises because JavaScript allows us to call methods on primitive types. For example, these are all legal statements –

1['toString']() // outputs 1 as a String

1..toString() // outputs 1 as a String. Note: 1. means 1 followed by decimal

true.toString() // outputs true as a String

"Some Str".toString() // outputs Some Str as a String

It is important to understand how this works. The Number 1, the Boolean true and the String “Some Str” are truly primitive types by themselves, but, when a method is called on them, JavaScript creates a transient or temporary object for the primitive type and tries to call the method. For example, in the case of the Number 1, a transient object is created as follows –

new Number(1) // Transient object

It is also important to understand that the transient object is ‘transient’ and is garbage collected as soon as the method has returned.
From the explanation and example above, we can see, this object like behavior of primitive types is a feature of the language and not of the primitive types themselves.

2. Passed by value vs passed by reference
As a rule of thumb in any programming language, primitive types should be passed by value, whereas, reference types, passed by reference. In JavaScript this is true, except for Strings.
So, Number and Boolean are passed by value. Whereas, everything else, including Array and Function( represented as objects in JS) are passed by Reference. So, what is the deal with Strings? Here is an explanation –

Since a String can be of infinite size, passing it by value will be inefficient, therefore, JavaScript chooses to pass Strings by reference. The good part is, Strings in JavaScript are immutable, meaning once a String object is created it cannot be modified. There is no method available on String that allows us to modify it. For example, Strings do not provide us any such method – insertCharAt or replaceCharAt. This also means, as Javascript developers, we do not have to worry about Strings ever getting modified, even though, they are passed by reference. Also, note, although, Strings are passed by reference for efficiency, they maintain their primitive nature when we compare two Strings. Take the following for example –

"abc" === ("ab" + "c") // true, since values are compared

In short, the issue of how Strings are passed in JavaScript is really not an issue because Strings are immutable.