Amortized Analysis - Dummies Overview

Introduction

 "Amortized!!! what the hell is that?" - is the first voice i would hear from any dummy like me. :) But when it comes to algorithms, performance matters. Algorithm is not something we write daily, (write and throw away code). That's the reason why along with algorithms, mathematics becomes a must. But with modern software engineering/agile ways of programming, mathematics is hidden in the form of requirements.

  Amortized - in my term means, paying your home loan using EMI option for life long. :) But the EMI balance reduces in long run as i pay up my interest first. It's is also associated with depreciation in general terms.
 

  But why would depreciation related to algorithms?

Concept

   Faster depreciation, we generally don't consider that product if it has a huge price tag. In algorithms terms, huge price tag (cost) is a big no no as we all know. But at the same it, algorithms require faster depreciation. That is, the cost should reduce when input size increases. How is that possible!!?? Who would need a product even though it costs less with faster depreciation? There are still people who buy made in china products. ;)

  

  Just Kidding.. Faster depreciation is not possible but at least there should be some balanced depreciation with the size of data an algorithm is processing. This is where we come with Big-Oh, Small-Oh, Smallest-Oh.. all that stuff!! :P

  But why that 'O'? There are many other letters in English. It's just the function naming similar to f(x) in mathematics. There are other functions as small-O, big/small-theta, big/small-gama for average/best cases. We use 'O' for indicating the worst case

More concepts

    Amortized analysis gives as ways to calculate like a banker, the cost involved in an algorithm by running through each and every line in code. The various ways to calculate are clearly given in many sites: the aggregate method, the accounting method, and the potential method (http://en.wikipedia.org/wiki/Amortized_analysis). Usually, algorithm designers use the above methods to optimize the algorithm for a longer run with huge data sets.

  More to come from scratch about algorithms.

 

Understanding Logarithms

            “During the periods of John Napier (http://en.wikipedia.org/wiki/John_Napier), he was called a magician for inventing easier ways to multiply. But now, the calculators and computers are the actual magicians for humans!!”

Introduction

            As the above quote says, the history behind logarithms is interesting and first we need to understand the problem which made mathematicians to think about using shorter ways. Mathematicians are seriously lazy people like us. :)

  Napier had been working on his invention of logarithms for twenty years before he published his results, and trigonometry tables (sin, cos table) was the origin of his ideas at about 1594.He wanted to simplify geometric progression by tabulating it and simplifying multiplications using additions. With the additive property of powers as the concept behind his approach (2^1 * 2^2 = 2^3), he started working out an approach to find a series for easy multiplication of 0.999. It was extended then to 10 in future.

10^1/2 = sqrt(10) = 3.162277 which means log(3.162277) = ½. Similarly, We can  continue for rational powers easily, as 10^3/4 = 10^1/2*10^1/4 = sqrt(10) * sqrt(sqrt(10)) = sqrt(31.62277) = 5.623413. which means log(5.623413) = ¾. I need to learn how sqrt values moves decimal points. J But this is how logs were calculated.

            This means that recording powers of a base present inside a huge number is what logarithms do.

More info

So simply, logarithms is the record of power of a given value,

log ₂8 = 3 which means 2^3 = 8. Logarithmic tables recorded the powers of huge decimals with high precision and preparing such tables is tedious job!!

Below is the logarithmic properties and b is the base.

1. log_b(xy) = log_bx + log_by.
2. log_b(x/y) = log_bx - log_by.
3. log_b(xⁿ) = n log_bx.          
4. log_bx = log_ax / log_ab.     

Example:

Log₂ 8 = log₂4 + log₂2

Log₂ 2³ = 3*log₂2

Some diagrams from MathFun:

 

Tail recursion–in detail

“The beauty of recursion is that!!.. - the beauty of recursion.”

Author speaks

  Sorry for not publishing any post nowadays. Tied up with lots of personal work. Now, would love to continue the series without gaps at least for some time. This promise is Without any GURANTEE, WARENTEE or any BONDS. :)

Metaphor

  If you catch something by tail, it tries to attack you using its head. :D

I think the below image will make you remember very well what is tail recursion.

Introduction

   Tail recursion is something that is more native to functional programming languages. In Maths, a tail recursive function is a function that expands itself.

Say, g(x) = f(x)

Then, tail recursion happens like this formula,        f(x) = f(g(x))

This means, f(x) = f(f(x)) = g(f(f(x)) = f(f(f(x))) … it goes on

This is purely useful for writing an mathematical logic which has a specific end condition. But this kind of recursion is majorly used in optimization of stack space in C++ and similar languages. Even some dynamic languages support this recursion type. But python doesn’t support it because of simple inherent problems for developers while using tail recursion.

Concept

   As i explained, tail recursion is mostly used for optimization & mathematical problem and widely popular in functional programming. The most and the perfect way a tail recursion works is really good for designing mathematically a computer program. But if you are normal novice software engineer, you just use this for optimization and only when its necessary because of its demerits:

• Stack doesn’t contain any footprint of the recursion happening. Compiler tries to expand the cycling recursion into instructions without using stack
• As there is no stack data, no way to debug such programs easily.
• Compilers might sometime fail to make the right jumps and data corruption can never be captured.

Already developers fight with pointers when this havoc adds more headache to it.

Programmers can think tail recursion as, just processing things using arguments itself and keep the returned value as the recursive call to the function. This makes the compiler to process the return value which expands the recursive calls in the single stack frame!!

Code

#include <iostream>

int fib(int n)

{

    if(n==0)

        return 0;

    else if(n==1)

        return 1;

    else 

        return fib(n-1) + fib(n-2);

}

int main()

{

    std::cout<<fib(7);

    return 0;

}

• Assembly is generated with tail optimization only when release mode is selected with Visual Studio C++.
• You can note that there is no stack footprint by the executable created by this, by tracing the disassembly.

Conclusion

Is it good or bad? based on the need and stack space savings requirement.

Infix, Prefix and Postfix notations

“Notations are created for easy processing of expressions. Polish and Reverse Polish Notations are popular ones. Normal notation is human readable.”

Introduction

  There are 3 kinds of expression notations: infix, prefix and postfix.

• Infix: is human readable. (2+3)*4
• Prefix: is readable with stack. Expressions first, values next. *+234
• Postfix: Values first, expressions next.  23+4*

Read more about the prefix notation here: http://en.wikipedia.org/wiki/Polish_notation

Prefix & postfix doesn’t need to use brackets and can be easily represented using stack or tree.

The main advantage is that we don’t need to care much about the precedence as in Infix notation.

Code

/*

Scan the given prefix expression from right to left

for each symbol

 {

  if operand then

   push onto stack

  if operator then

   {

    operand1=pop stack

    operand2=pop stack

    compute operand1 operator operand2

    push result onto stack

   }

 }

return top of stack as result

*/

void main()

{

    char* str = "*-5 6 57";

    StackList opStack;

    int d, sum = 0;

    int result=0;

    int count = 0;

    char* rstr = str;

    while(*rstr != '\0') rstr++;

    rstr--;

    while(rstr > str-1) {

        if(isdigit(*rstr)) {

            d = *rstr - 48;

            if(count == 0) sum = d;

            sum += d*count*10;

            count++;

        } else {

            if(sum != 0) {

                opStack.push(sum);

                sum = 0;

                count = 0;

            }

            switch(*rstr)

            {

                case '+':

                    opStack.push(opStack.pop() + opStack.pop());

                    break;

                case '*':

                    opStack.push(opStack.pop() * opStack.pop());

                    break;

                case '-':

                    opStack.push(opStack.pop() - opStack.pop());

                    break;

                case '/':

                    opStack.push(opStack.pop() / opStack.pop());

                    break;

            }

        }

        rstr--;

    }

    cout<<opStack.pop();

}

• We need to come in reverse and push into stack the integers
• When we see a operator, we need to operate the top 2 elements in the stack.
• Note that, we use space as the delimiter between 2 digits. For operators, we don’t need that
• In the stack we will have the only element which is the processed output of the expression

Probability for Dummies

"The various possible ways are decided using permutation or combination. But what is the possibility that a arrangement can occur is called probability.. Randomness in this world requires probability to predict..!! All game plays are made with some defined principles and randomness..But how to measure at least well defined randomness so that to predict something? plainly with probability"

See Also
http://analgorithmaday.blogspot.com/2011/05/set-theorya-dummies-guide.html
http://analgorithmaday.blogspot.com/2011/05/permutations-combinations-for-dummies.html

Introduction

  In mathematics, you have deterministic or non-deterministic problems. All non-deterministic problems are called probabilistic problems. Simply, All math done with formula's are deterministic..!! Even for generating randomness, we use formula's. But note that these are non-deterministic formulas!!.. You can never say when they will fail!!.. a formula should never fail right ? :)

   The beauty of probability is to check how much we can pass/fail rather than simply pass!!.. It is sometimes just a condition over permutations/combination. That is, reason we studied about permutation & set theory well before.

 Pass/Fail means Probability.. Which means.. Pass = 1, Fail = 0. So the value of probability will lie between 0 and 1.

If probability of some event is 0, then it means it will never occur (utter fail or flop). If its 1, then it will definitely occur(success).

What is the event a probability measure? By now, you would have guessed. Random and known time interval occurring events. But we need to put some question for which we need to calculate probability (it can be either % failure or % success calculation).

The common example, flipping coin. The probability of getting tail 50%. The probability of getting head is 50%. Because the event is equally likely. You will either get a tail or head with equal probability.

But not all events are equally likely like this. Lets take an example question like this.
A couple has 2 kids and atleast one is a boy. What is the probability that both are boys?
Get the permutations of 2 kids: GG, BG, GB, BB.. 4 arrangements. Since we only care about probability of getting 2 boys, Ignore GG. Total 3 arrangements in which we find a boy out of which only 1 has both of them as boys.
So the probability is: 1/3

Concepts (Math)
Some more math about Probability Point-by-Point.

• Probability values are always between 0 and 1. So, it also like 0% possible, 100% possible
• It operates over a sample space called Experiment(E). It's nothing but the set of all the permutations. The set of permutation changes based on the kind of probability question we ask!!
• We call some thing as event if it occurs once in the experiment. Event is nothing but subset in the Experiment set. We calculate the probability of an Event in the experiment!!
• All set theory concepts applies to our experiment set(sample space). You can combine two experiments (Union). You can take common events across Experiments(Intersection). You can even take difference between two experiments.
• Disjoint sets as we already studied means empty set when you take intersection between them. Same case applies here, disjoint events means no relation between the two events.
• If you have two events and you know that always 1 event occurs, then we can use conditional probability. Conditional probability is nothing but taking intersection between the two events. (take randomness of only common events)

Some more concepts
  Sampling is a statistical concepts. Probability too works with samples. There are many more mathematics part of statistics like  differential equations and integrals. Distributions are all defined with differentials and integrals. Distributions are basically used to generalize the function. The same distributions can be used to generalize a probability function as a random variable. This is called Probability distributions.

  Whatever probability you have, the probability distribution runs from 0 to 1 and also there will be a mean value between these two numbers.
Example: If there are large number of trails of tossing the coin, then heads will be the max with probability around 50%.

Where it is used ?
Probability and expected value function is a must to know to analyze the random algorithms. We studied all this just because we are going to study randomized algorithms :).

It is known that the randomized algorithms perform really well in average case for specific problems.

More about Probability
  I would suggest referring a better math book rather than me writing about it. There are many more formulas and most used probability functions. Please refer a proper book.

Permutations & Combinations for Dummies

“I never understood concepts like permutation, combination which is quite confusing. But permutation is nothing but just a way to count all possibilities of a nested iteration!!”

Introduction

  Just take, the following nested for loops

for(int i=0;i<m; i++) {

 for(int j=0; j<n;j++) {

   cout<<i<<":"<<j<<endl;

 }

}

Simply we can tell directly the total iterations are m*n. But the traversal done by the loop with an array will be like..

REPEAT –> read the row –> read from left to right –> move to next row –> UNTIL i*j == m*n

These are the various values comes out considering m=3, n=3,

{0,0}, {0,1}, {0,2}

{1,0}, {1,1}, {1,2}

{2,0}, {2,1}, {2,2}

Keeping i, we iterate with changing symbols in j.. Doesn’t it look like Cartesian Product with a Condition?

This kind of rearrangement of numbers are necessary to traverse the array. Similarly you need rearrangement of numbers in various applications!!..

For example, say, you need to find all possible rearrangements of a shuffled 56 deck card.. There are numerous ways if you need to find the rearrangements of all the 56 cards(56!).. But if you want to know rearrangements possible when the cards are distributed within 14 people..

You just need to count 14 possible rearrangements out of 56 cards to calculate. This is where you need permutation..

To understand permutation well, you need to understand set theory!! Especially Cartesian Product!.. Learn about set theory first: http://analgorithmaday.blogspot.com/2011/05/set-theorya-dummies-guide.html

Concept

   Every multiplication can be represented with a set of additions. When you add a number that much times, you get the multiplied value. Similarly, if you have a set of 3 numbers.. how would need to find the number of ways it can be rearranged?

Strings

   If you take Cartesian product of same set k times with each set having some n symbols in it, you get strings. S^k sets with each having n items.

i.e, If the set is S, S x S x S is a 3-set product. If you have only 2 elements in it, then total you get 2^3 distinct elements as a result of this product. This count of distinct elements can be got from n^k equation. Example, Take a binary string of length 3. You have max 2 symbols possible in a binary. Total possible sets are,

000,001,010,011,100,101,110,111

Which is 2^3.

Permutation

Permuting means, simply re-arranging without missing any symbols!!.. if you want the number of rearrangements what would you do ? That’s where permutation comes into picture.

For example, saw you have a set {a,b,c}. The total number of ways, you can order this variables are,

abc, acb, bca, bac, cab,cba

Total 6 ways, the above 3 char array can be permuted. This gives as a pattern, the first element is chosen n ways, the next ignoring the first element chosen in n-1 ways, the next in n-2 ways. This means, you get n(n-1)(n-2) which is nothing but n!

If in the same above array, you just need to know the permutation of only k-elements instead of all n elements. (n is the total elements in the array).  ex: this is similar to finding the 14 cards possible rearrangements in 56 card deck..

then, the total ways are,

ab, ac, bc, ba, ca, cb

Again the same, 6 ways. But now, n, n-1, n-2 and upto n-k+1 is what required. So, The formula becomes like below,

Combination

We already saw about Strings which we get by Cartesian product of the same set and get the unique items out of the set with each symbol in an order.

Combination has the same property of getting unique items with each item at one place but ignores the order of items requirement. It considers symbols in both the set and takes out in-order uniquely!!.. i.e, You should remove transitive, symmetric symbols in a combination!!

Ex: Permutation for 2 element in a 4 element set, {a,b,c,d}

ab,ac,ad,ba,bc,bd, ca,cb,cd,da,db,dc

Total 12 sets are possible since we need to consider every re-arrangement in any order.

Combination for 2 element in a 4 element set, {a,b,c,d}

ab, ac, ad, bc,bd, cd

There are only 6 sets!!.

Formula:

Examples

Some real world example!!

http://betterexplained.com/articles/easy-permutations-and-combinations/

You have 8 players.. and 3 different cups to be won. Gold, Silver, Bronze. You give each cup to only one of the players and the cups will be given in the order, Gold->Silver->Bronze.

Gold: When you need to give Gold, you have all 8 players competing for it. So, total 8 options possible.

Silver: When you need to give Silver, you have already given Gold, so only 7 options possible

Bronze: When you need to give Bronze, you have already given Silver, so only 6 options possible.

Total ways in which the 8 players can win will be 8! ways..

But, there are only 3 cups, so Total ways in which the top 3 cups can be won, if given one-by-one in order to the persons will be: 8 * 7 * 6.

This is where Permutation comes into Picture!

If the price money is same, i.e, a Stainless steel plate. You don’t need to care about the order in which the 3 cups are given. So, its 3 cups given to 8 players. But 3 cups re-arrangement don’t need to be taken into account as all are equal. So 3! ways of arranging the cups(6 ways) are useless when it comes to just picking some 3 out-of-8.

This is combination and you get only: 8*7 ways according to the formula.

Set Theory–A Dummies Guide

“If its possible to express the world in a set, a mathematician would do that!! :) The power of sets are vast that its used in statistics and computing a lot!!. To understand algorithms clearly, you need to understand set theory!!”

Background

    I am assuming that, the reader already know a little bit about Sets. Sets is a collection of unique objects. There is natural(without negative) number set, real number(floating point) set, integer(with negative) set. You can also have sets with different symbols. But the major operations that can be done between two sets, A & B, are:

• Intersection: common items between A & B , $A\capB$
• Union: all unique items between A & B (common items appear only once)  $A\cupB$
• Difference: if its, A-B, then items in B if present in A are removed and you get remaining elements.
• Disjoint: both A & B don’t have any items in common

I assume you understand the above general and basic concepts to move on into More details

Point-By-Point

   Extra concepts which you might require in some problem solving & algorithms are,

• singleton set: a set with only 1 element in it.
• partition of a set: a set if gets partitioned into subsets of size>0.. its called a partition. [Check here: http://en.wikipedia.org/wiki/Partition_of_a_set]
• complement of a set: If you take a set A, complement of set A is the elements which are not present in A. $\bar{A}$
• universal set: $A\cup\bar{A}$ is a universal set which includes all the elements in the bigger set
• n-set: If you have “n” elements in a set, its called n-set,
• k-subset: If you have “k” element subset from a “n” element set, its called a k-subset of the bigger set.
• Cartesian product set: Its the product of two sets.. straight to straight!! A x B = {a,b} x {a,b} = {(a,a),(a,b),(b,a),(b,b)}
• binary relation set: subset of Cartesian product between sets. For example, if A & B are subsets in a Natural number set and a relation is defined between the elements in the sets, like, a<b, for a in A, b in B, then, it means, the two sets A & B has elements sorted in ascending order when combined!!
• equivalence relation between sets: is a type of binary relation set!! but the sets will contain elements which are disjoint and exhibit equivalence among each other!!.. i.e, two sets are equivalence sets only if they are part of a same set under a binary relation
• equivalence class: the condition of equivalence between two sets should hold in all the elements of the class set!!.. i.e, if you need a set of even numbers from a natural number set given an even number, define a relation such that, equivalence is hold, like a+b is even..
• functions: extension of Cartesian product. Instead of just Cartesian product, we place a function with a binary relation among elements in the set

Practical Applications

• The main application will be on Graphs!! :) We will study about it soon. We have all the set concepts in a graph!!
• As it can put in Graph, Tree is just a subset of Graph!!.. Tree concepts are all derived from the set theory!!
• Binary trees we studied are disjoint sets composed of: root node, left sub tree, right sub tree. Disjoint means, all these 3 sets should have completely different nodes!! It’s not necessary to have any nodes as well. This makes, Binary tree a special case of Trees.
• Partition of a set can be directly related to substring, subsets in an array etc.

Example: The set { 1, 2, 3 } has these five partitions:

• { {1}, {2}, {3} }, or 1/2/3.
• { {1, 2}, {3} }, or 12/3.
• { {1, 3}, {2} }, or 13/2.
• { {1}, {2, 3} }, or 1/23.
• { {1, 2, 3} }, or 123

This is clearly how python lists work!! :). Python and Perl both have splice, union, intersection of arrays/lists.

• Red-black tree’s & Graph colouring all uses the set theory principles to distinguish different coloured nodes
• Equivalence relations are used in extracting subsets which exhibit equivalence. The famous subset sum problem(http://www.codechef.com/problems/PAIRSUM/).
• Functions over a set can be used to extract elements matching a binary condition!! we use nested for loops & if conditions to do this actually :)

Random number generation logic - Linear congruential generator

“Randomness is really important for probabilistic actions. Like card shuffling, coin tossing etc. How can we represent that in a machine? There are lot of random number generators available!!”

Introduction

  Random number generators have huge application space mainly in Cryptography. But we need this random number generators for the articles we will soon start studying about, HASH TABLES!! :) You need random unique keys for storing the values so that search is O(1) similar to an array.

  There are types of randomness however!! Pseudo Randomness & “True” Randomness!!.. All proven with heavy mathematical theorems. “True” Randomness is really important for security algorithms like RSA. But if the randomness fails and a pattern appears, you get to crack the security system as well!! :)

   Randomness is mystic and same as how our universe behaves :) So impossible to get true randomness without leaving it to run around the world.

  Watch this movie to understand how tough it is.. :) It’s about a Math scientist trying to find patterns and suicides with a head gun shot http://www.imdb.com/title/tt0138704/ (Psycho movie.. Beware)

  Ok, into the business. let’s get into some simple random generators!!

Concept

       LCG – Linear Congruential Generator is a method to generate pseudo random numbers until a particular range. After that range, the numbers would start repeating. This range value is also called as “seed”.

 

— the "modulus"

— the "multiplier"

— the "increment"

— the "seed" or "start value"

Source: http://en.wikipedia.org/wiki/Linear_congruential_generator

The random value can go up to  MAX = “m”. single linear congruent equation usually repeats numbers. To avoid that, we have a multiplier “a”. We can either keep “c”, zero or non-zero.

If you have only “a”, then its called multiplicative congruential method.

Note that, the values of m, a, c decides the amount of randomness you get with this function. The values of these numbers are experimented and must have noted properties. :D

Refer the Wikipedia link for more details.

In C/C++, mostly we use time() function as the seed which gives us good precision. like below,

   srand(time(NULL));

After that, we set the modulus value “m”, by giving the rand a value,

   rand() % 500;

The above will generate a random number below 500 with X₀ = system time + the above suitable random multipliers. But you should note that, if you iterate 1000 times the above rand function, you will start getting the same numbers frequently.. we should get at least the first 500 times the different number!!.. But even that won’t happen :D

How this recursive function generated different numbers ?

The above plot will show you how the values get randomly distributed!!. Note that, this is happening just because m and a are prime..!!

Check more plots here: http://demonstrations.wolfram.com/LinearCongruentialGenerators/

Code

Try the below code:

void main()

{

    srand(time(NULL));

    for(int i=0;i<1000;i++)

        cout<<": "<<rand()%100<<endl;

}

I got the following last set of output with “8” straight-to-straight repeated. Just with a difference of some 2 extra iterations!!..

Output

: 8

: 18

: 37

: 8

: 33

: 14

Concept behind Order Statistics

“How many times you would have required to get a kth smallest number in a set of numbers? It’s a must in many applications. Moreover, the most used is the minimum & maximum in a set of numbers. Although we have lots of O(1) data structures to get min/max, if we get numbers as an array!! we need to reorganize which still takes more time. This is where Order statistics comes into picture”

Introduction

We have seen lots of sorting methods, String analysis algorithms. As we see that the most common algorithmic methods are: sorting & searching. But there is one more, which is selection methods!!

Selecting what is max or min in a set is really simple and also the most used operation in any big programs.

Let’s see an example of a selecting problem in an interview perspective. One of the most asked question is:

Find the buying and selling price of the stock so that we maximize profit. We are given the array of stock prices. (with O(n) time and no extra space)

How would you solve this problem? There are many more related problems like selecting football team members based on the score profiles they have. In Cricket especially, the initial members considered by the board would be the players who have good economy and the computer basically prepares that list. :)

Even you can run an algorithm to find the players in the panel if you know all of their economies!!.

For this a layman way could be to use sorting and then select the top 10 or 20. But it’s not just sorting and elimination since all comparison based sorts take O(n log n) time.

What we need is O(n) time which is linear time.

So the main problem here is, How would you get k-th smallest or largest element in an array with O(n) linear time ?

Concept

What does it mean by k-th smallest element ?

If k=1, then it means the smallest element..

if k=n, then what we get would be the largest element in the array

This ‘k’ which can even decide the sorted order of the elements in the array is the base concept of Order Statistics.

Quick sort, Merge sort and almost all comparison sorts tries to find this ‘k’ of each element in the array so that we can place the elements in the right positions.

We also studied about O(n) sorting methods(counting sort, radix sort) which tries to find this ‘k’ without comparisons. :) Similar to those, we need a selecting method, if our requirement is to just find the k-th position code.

First we will see basic code of finding max & min with lesser constant time.

Code

void getRange(int *arr, int size)

{

    int min=INT_MAX;

    int max=INT_MIN;

    for(int i=0; i < size; i++)

    {

        if(arr[i] < min)

            min = arr[i];

        if(arr[i] > max)

            max = arr[i];

    }

    cout<<min<<","<<max;

}

void main()

{

    int A[] = {2,5,1,8,9,13,4,14,6};

    getRange(A, 9);

}

• The above code takes O(n) time and n comparisons as well to determine min & max
• This can be made faster!! Yes!! Avoiding constant time in a code really optimizes the code!!.. Always try remove constant time when you want optimize code!! :)
• The optimizations possible
  • Setting up initial values of max & min don’t need to at extremes
  • If the size is odd, set min & max to A[0]
  • If the size is even, compare first 2 elements, minimum goes to min & maximum goes to max
  • The above kind of initialization reduces comparisons to n-1.
  • But still we need both max & min here, so we still have 2n-2 comparisons (from n comparisons).
  • next optimization is: comparing in pairs!! which would bring down our comparisons to 3(n/2) :).. Below code does all these optimizations

void getRange(int *arr, int size)

{

    int min;

    int max;

    int start=0;

    if((size & 1) == 1) {

        min = arr[0]; 

        max = arr[0];

        start = 1;

    }

    else {

        if(arr[0] < arr[1]) {

            min = arr[0];

            max = arr[1];

        }

        else {

            min = arr[1];

            max = arr[0];

        }

        start = 2;

    }

    for(int i = start; i < size; i+=2)

    {

        int smaller;

        int larger;

        if(arr[i] < arr[i+1]) {

            smaller = arr[i];

            larger = arr[i+1];

        }

        else {

            smaller = arr[i+1];

            larger = arr[i];

        }

        if(min > smaller)

             min = smaller;

        if(max < larger)

            max = larger;

    }

    cout<<min<<","<<max;

}

void main()

{

    int A[] = {2,5,8,9,13,4,14,6};

    getRange(A, 8);

}

• Although the above code looks bigger, the comparisons are lesser and our problem domain got divided. n/2 :)
• We have some how divided the problem /2 using optimization. But more cleaner optimization possible if we know the Median!!
• We will learn about Median in next article!!

MIT Video

MIT order statistics lecture

The above video explains all algorithms in selection method. We will see all these methods in coming blog entries.