Using The Master Theorem To Find the Big O Of Recursive Algorithms

Posted on Updated on

For some persons finding the Big O of recursive algorithms can prove to be difficult especially if the algorithms are complexed. The Master Theorem provides a relatively simple way to solve recurrence relations as long as the recurrence fits the theorem constraints.

Basic definition:
T(n) = aT(n/b) + f(nc) where a >= 1, b > 1, and c >= 1
T(n) = Θ(nc) if c >= logba
T(n) = Θ(nc log n) if c = logba
T(n) = Θ(nlogba) if c < logba

We can think of “b” as the number of branches and “a” as the number of recurrences done; lets take a look at the example.

If we have a function:

def binary_search(seq, value):
    if len(seq) == 0:
        return False
        mid = len(seq) // 2
        if value == seq[mid]:
            return True
        elif value < seq[mid]:
            return binary(seq[:mid], value)
        elif value > seq[mid]:
            return binary(seq[mid + 1:], value)

T(n) = 2T(n/1) + f(n0) : a = 1, b = 2, c = 0

log21 = 0 therefore c = logba which satisfies Θ(nclog n) = O(log n)


Monads And Their Applications in C#

Posted on Updated on

If you have ever written code in most modern programming languages and even languages that are not functional in nature there is a very high probability that you have used some form of monadic structure. A monad is a structure that represents computations defined as sequences of steps: a type with a monad structure defines what it means to chain operations, or nest functions of that type together. This allows the programmer to build pipelines that process data in steps, in which each action is decorated with additional processing rules provided by the monad. As such, monads have been described as “programmable semicolons”.

Monads allow you to do things like method chaining, and flattening null and exception checks in highly nested code blocks.

Monadic Rules:

1.  Left identity
Identity.Compose(f) = f

2.  Right identity
f.Compose(Identity) = f

3.  Associative
f.Compose(g.Compose(h)) = (f.Compose(g)).Compose(h)

Example: Very basic Monad to factor out division by zero check in BMI calculation.

void Main()
    var me = new person{name = "Romaine", weight = 170, height = 83};
    Console.WriteLine(new Maybe<int>(me.height).bind(() => new Maybe<int>((703 * me.weight) / (me.height * me.height))));

class Maybe<T>
    public T value;
    public Maybe(T val)
        value = val;
    public Maybe<T> bind(Func<Maybe<T>> func)
        if(value == null || value.Equals(0))
            return null;
        return func();

class person 
    public string name;
    public int weight;
    public int height;

Monads are awesome, and I still have a lot to learn about them, however I can already see them everywhere in C#: IEnumerable, JQuery: Ajax Requests and lots more.

Until next time keep learning :)


From MATLAB To Python

Posted on


For many years MATLAB has been my primary tool for prototyping algorithms, because of its rich set of optimization functions and the AI tool box it has proven to be a valuable tool to have. However, It is not cheap and if you do not have a company to pay for license or attend a university that provides you with a license then you will have to find an alternative.

MATLAB is not a programming language rather its a tool that has as part of its framework a programming language called M language, this language has a lot of quirks and takes some getting use to, the other issue I found with MATLAB is that the functions while well documented do not seem to follow a standard in terms of parameters; on the whole while MATLAB is a good tool for prototyping and is used a lot in engineering and medical fields which are my core domain; However,I am forced to look for a cheaper/free alternative that will give me as much if not more tools than MATLAB now provides.

Python to the rescue:

Python is powerful… and fast;
plays well with others;
runs everywhere;
is friendly & easy to learn;
is Open

All these wonderful things make Python a big contender for my MATLAB replacement.

The first thing we want to do is install Python.
Next install my favurite Python IDE PyCharm
Create a new Python Project using PyCharm
Python project

How do we add packages to our project?
Python is nothing without its packages and two of my favourites are numpy and scipy. To add these packages simply download the Anaconda distribution and configure it to be your default python implementation.


And here is my first piece of python code as taken from the python website :-)


All I need now is a good Python book and 2-4 months to delve into the language. Stay tuned for more posts on my Python journey. Happy coding!!

Finding stuff in SVN Source control with PowerShell

Posted on Updated on

Its as simple as this:

svn list -R [your svn repo url] | select-string [string to search for]


Posted on Updated on

This little code snippet converts MATLAB Struct to xml, enjoy!!

%Convert Struct to XML

function obj = struct2xml(param)
   doc = com.mathworks.xml.XMLUtils.createDocument(inputname(1));
   root = doc.getDocumentElement;

   obj = xmlwrite(parse(param, doc, root));

function obj = parse(param, doc, root)
   if isstruct(param)
      fields = fieldnames(param);
      for i = 1 : numel(fields)
         if isstruct(param.(fields{i}))
            write(doc, root, fields{i}, '')
            parse(param.(fields{i}), doc, root.getLastChild)
            write(doc, root, fields{i}, param.(fields{i}))
     doc = 'could not convert';
   obj = doc;

function write(doc, root, pname, param)
   if isempty(param) == 1
      elem = doc.createElement(pname);
      if ismatrix(param)
         val = mat2str(param);
         val = num2str(param);

How To Unit Test A LINQPad Code Snippet

Posted on Updated on

Writing code is a programmers life; sometimes it becomes necessary to write pieces of code that you can conveniently run and evaluate  without spinning up a full fledged IDE. For those tasks there is a tool called LINQPad. LINQPad allows you to write/run snippets in C#, SQL and a few other languages. In oder to run the example in this tutorial you will need to download LINQPad and NUnit Lite.

After installing LINQPad and NUnit Lite open an instance of LINQPad and change the language to C# Program.


Next hit the F4 key on you keyboard to bring up the additional references dialog and browse to the location where you installed NUnit Lite. You will need to add NUnit Lite as a reference.


Copy preceding code into the LINQPad edit window then hit the run button, the results of the test will be displayed in the console window, enjoy :-)

void Main()
	new NUnitLite.Runner.TextUI().Execute(new[]{"-noheader"});

public class Dog
	public string Howl()
		return "awhooo!";			
	public string Growl() {return "Gerrrr!";}

public class DogTest
	Dog fido;

	public void init()
		fido = new Dog();
	public void Howl()
		NUnit.Framework.Assert.AreEqual(fido.Howl(), "awhooo!", ":-(");
	public void done()
		fido = null;