Searching algorithms Part 1.

This is the entry for Week 7 and Week 8.

This week t'was a good week, because I finally saw some beautiful code on my lecture slide.

My eyes teared up when I finally saw this piece of beautiful code.

The code above shows a linear search algorithm.  But what is Linear Search anyway?

Let me explain in layman's terms:

Imagine that you have a stack of cards and you want to find a card with a certain rank, for example "Jack", how would you implement that method of search?

Say, you also have gun to your head so that you would search fas.. yeah
I believe I'm overthinking this hypothetical scenario.

How would you do it?

Answer: (Most probably) go through each card one-by-one searching for a Jack.

Me: Hooray! You can do Linear Search!

Linear Search is the most obvious search algorithm: going through a list or array one element at a time, in order. It isn't terribly efficient either...

Given that the course has finally covered enough logical material to cover an algorithm, we have also covered enough material to develop a tool to analyze the algorithm.
That tool is called big-Oh

Big-Oh effectively catalogues functions by their rate of growth.
I personally though such a concept is effective, as it allows us to distinguish functions of different growth rates.

Consider the functions:

$2n^2$, $12n^2 + 100$, $10^6n^2 + 10^{6^6}$

despite the large variance in the coefficients of the functions above, we can prove that
there is a certain point of $n$ beyond which a multiple of the function $n^2$ will out-grow all the functions above.

Hence we say these functions are in $\mathcal{O}(n^2)$

In mathematical presentation $\mathcal{O}(n^2)$ is represented as:

$\mathcal{O}(n^2) = \{f:\mathbb{N}\Rightarrow \mathbb{R}^{\geq 0} | \exists c \in \mathbb{R^+}, \exists B \in \mathbb{N}, \forall n \in \mathbb{N}, n\geq B \Rightarrow f(n) \leq cn^2 \}$

Phew! A lot of notation.

Initially, I found the idea of big-Oh to be absurd, as I found it hard to swallow the fact that even extremely small coefficient quadratic equations and extremely

large coefficient quadratics fit in the

same big Oh, surely $1000000000x^2$ grows faster than $x^2$?

I will talk more about big-Oh in the next post...