Humans somehow construct opinions that may conflict with each other. How do you determine that something is true? Seriously, how do you determine that a statement is irrefutably true? If you can say that a particular statement is irrefutably true then those people who disagree can be fairly called illogical. More importantly, we can confidently build knowledge upon it.

# Category Archives: Mathematics

# Linear Search Time Complexity Analysis: Part 4

In Part 2 of this series, we have seen one way to determine the average-case running time of linear search. We have used the following lemma without proving it:

Now I will prove the correctness of this indentity. Continue reading

# Linear Search Time Complexity Analysis: Part 3

In the previous part we determined the average-case running time of linear search when **x**, the element we are looking for, appears at least one time in a given array **A**. In this part, I will show a simpler way to determine the average-case running time. Continue reading

# Linear Search Time Complexity Analysis: Part 2

Welcome to the second part of the series in which I will provide an analysis of the average-case running time of linear search. This turns out to be so much more fun than what I have expected. Recall that we are considering three cases depending on how many times the element **x** appears in **A**. Continue reading

# Linear Search Time Complexity Analysis: Part 1

Linear search is one of the simplest algorithms. Consider an unsorted array **A** of size **n**. Given an element **x**, we would like to determine whether **x** exits in **A** or not. Linear search goes like this: search **A** for **x** in order by considering **A[1]**, **A[2]**, …, **A[n]** until either it finds **A[i] = x** or it reaches the end of the array which means that the element does not exist. Because the algorithm always starts at 1 and continue sequentially up to **n**, we call it *deterministic*. We don’t make any assumptions about whether **A** contains one or more equal copies of the same element. However, we assume that the elements of the array, whatever they are, are equally likely to appear in any order. Also we will consider only the number of comparisons that involves elements from **A** when computing the running time. Continue reading

# The 3x+1 Conjecture

The 3x+1 conjecture is a very famous open problem in mathematics also known as the Collatz conjecture. It is known to be the simplest open problem such that a child with elementary math knowledge can understand it. Continue reading