Building Blocks, Analysis of Algorithms & Rates of Growth –Part 2

In the previous tutorial (Part 1) we briefly described how to mathematically describe an algorithms running time or number of basic operations based on a input “n”, although informally.

I’ve read several books on Algorithms & computation and several dozen articles or papers on the subject, however I find the book “Introduction to Algorithms” By Cormen, Leiserson, Rivest and Stein to be the best in terms of explaining Algorithmic analysis.

This book has become so popular that it is known as CLRS (Acronym formed by the authors 1^st names).
Let’s briefly review rates of growth exhibited by most Algorithms:

Rates of growth in order:

Log₂ n < n < n log₂ n < n² < n³ < 2ⁿ

So let’s again, informally describe the code sample below:

Now let’ analyze the above code snippet :

1)      There is a 1 time variable declaration in the outer loop “int i=0”

2)      The expression “i<10” is evaluated 10 times, and if true “i” value is printed 10 times

3)      The “int k=0” is declared for the inner loop per every “i” outer loop’s iteration

4)      The expression “k<10” is evaluated 10 times, and if true “k” value is printed 10 times

5)      The inner loop iterates “k++” 10 times , per every “i” outer loop’s iteration

6)      The outer loop iterates 10 times “i++”

There are about 430 basic operations, and that can vary based on implementation.

Roughly speaking,  each loop iterates 10 times & prints the value of “I” per iteration and per every iteration the inner loop  iterates 10 times & executes 10 prints, so 20x20=400. If we replaced 10 with n in the “i<0” and “k<n” , then we get n *n , n² executions.

As you can tell although correct, our observation is very wordy and inconsistent because there are many ways to implement the same loop, therefore we need a consistant , implementation dependent, and easily understood method to describe algorithms.

Formal method for analyzing algorithms:

 According to CLRS “When we look at input sizes large enough to make only the order of growth of

the running time relevant, we are studying the asymptotic efficiency of algorithms.

That is, we are concerned with how the running time of an algorithm increases with the size of the input in the limit...”.

 In our explanation we calculated that the outer & inner loops has 430 operations, but taking into account the major feature of the code snippet can be simplified to n² operations, therefore we are ignoring insignificant operations known as constants “c”, for large input “n”.

We have 3 major notations to describe algorithms (Summarized from CLRS):

Θ - notation (Theta)

For a given function g(n) we denote by Theta (g(n)) , pronounced “Theta g of n”

Theta(g(n)) = {f(n) such that there exist positive constants c1,c2,and n0 , such that 0<=c1g(n)<=f(n)<=c2g(n) for all n >= n0.

“A function f(n) belongs to the set Theta(g(n)) if there exist positive constants c1 and c2 such that it can be sandwiched between c1g(n) and c2g(n) for sufficiently large n”(CLRS).

In terms of our outer loop & inner loop example , the code snippet code be describe as Theta(n²), meaning there is no way the code will execute in less than n² operations and no more than n² + some constants c, hence Theta(n²).

O- notation (Big O)

Big-O notation for describing maximum number of operations, or max running time (upper bound)

For a given function g(n) we denote by Theta (g(n)) , pronounced “Big-O , g of n ”

O(g(n)) = {f(n) such that there exist positive constants c and c0 such that 0<=f(n)<cg(n) for all n>=n0.

In terms of our outer loop & inner loop example, the code snippet code be describe as O(n²),

Meaning there is no way the code will execute in more than n² + some constants c . Since the loop is the dominating feature and there is n operation per loop and inner loop is nested in the outer loop therefore n2 + constants operations, there exist a third nested loop or any other feature that dominates n2, lets say n3.

Ω - notation (Big Omega)

Big-Omega notation for describing minimum number of operations, or minimum time (lower bound)

Ω (g(n)) = {f(n) such that there exist positive constants c and n0 such that 0<=cg(n)<=f(n) for all n>= n0.

In terms of our outer loop & inner loop example, the code snippet code be describe as Ω(n²),

Meaning given large enough input or there exists inputs, such that the running will not less than n² operations, regardless of implementation.

If a function or algorithms complexity can be described as Theta(n), Theta (log n), or Theta etc.., than it also implies O(n),O(log n), O etc and Ω(n), Ω(log n), Ω etc, this is because range in Theta automatically implies Big-O and Omega, but not the other way around.

I heavily referred to CLRS chapters 2 & 3 , for more detailed explanation please read URL:

Going forward we will be primarily using O “Big-O” therefore describing the upper bound for running time of algorithms.

Now let’s state the running time of basic mathematical operations addition, subtraction, multiplication, division, etc.

	Upper Bound
Addition	O(n)	Basic or School book method
Subtraction	O(n)	School book method
Multiplication	O(n2)	School book method
Division	O(n2)	School book method

(http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations)

Note: There are more efficient methods for multiplication and division , we will encounter them later.

Examples:

1.For each of the following code fragments, give a Big-Oh analysis of the running time in terms of N:

    (a)

        for ( int i = 0, Sum = 0; i < N; i++ )     

            for( int j = 0; j < N; j++ )           

                Sum++;           

Well each loop is O(n) operations or linear running time, and we have a nested loops which terminated based on the variable “N” , therefore n² operations + addition which is n operations , therefore O(n²) running time or quadratic.

(b)

       for( int i = 0, Sum = 0; i < N * N; i++ )  

            for( int j = 0; j < N; j ++ )          

                Sum++;     

The 1^st loops running time is dominated by multiplication which is O(n²). The nested loops execution is based on this expression “j<N”. N’s value in the inner loop is determined by multiplication, from the outer loop thus O(n²)*n , simplifies to O(n³) running time,  or cubic.

(c)

      for( int i = 0, Sum = 0; i < N; i++ )      

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

                Sum++;                             

The 1^st loop has O(n) running time, however the running of the nested loop is defined by analyzing the expression “j<i” , “j” must be “i-1” for the inner loop to execute at each iteration thus n * n -1 = n² – n , simplifies to 0(n²), thus quadratic.

         (d)

         for( int i = 0, Sum = 0; i < N; i++ )      

            for( int j = 0; j < N * N; j++ )       

                for( int k = 0; k < j; k++ )                           

                          Sum++;

The 1^st loop has n operations, the 2^nd loop is nested and performs n² operations, and the third loop performs n-1 addition operations, thus f(n) = n[n²(n-1+n)] ,simplifies to f(n)=n⁵ operations, or O(n⁵) running time, thus exponential.

2. An algorithm takes 0.5 milliseconds for input size 100. How long will it take for input size 500 if the running time is:

 a. Linear

f(n) = 0.5 millisecs * (n/100)

f(500) = 2.5 millisecs

 b. O( N log N) 

f(n) = [0.5 (n log n) / (100 log 100) ]

f(500) = 3.373  millisecs      

c. Quadratic       

f(n) = 0.5n²  / 10,000      

f(500) = 12.5 millisecs

 d. Cubic

f(n) = 0.5n³ / 100,000  

f(500) = 625 millisecs

3. Find the Big-O for the following functions:

    (a) f(x) = 2x³ + x² log x           

O(x³)

    (b) f(x) = (x⁴ – 34x³ + x² -20)

O(x⁴)    

    (c) f(x) = x³ – 1/log(x)                       

O(x³)            

We are finally finished with part 2.

In part 3, we will discuss Recursion and its running in detail.

References

1.       Cormen, Thomas, Charles Leiserson, et al. Introduction To Algorithms. 2nd. Massachusetts: MIT Press, 2009. 41-48. Print.

2.       http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

Building Blocks ,Analysis of Algorithms & Rates of Growth

I thought it would be prudent to split this tutorial into 2 parts, in order to avoid bombarding the reading with too much information.

The most important accept of analyzing algorithms is to figure which features in the algorithm ultimately define its efficiency, therefore ignoring the minute features. This is the only way we can describe the performance of algorithms across different platform & implementations.  

Not all computers have the same specification or architecture ; some computers are PC’s others are Apple Macintosh, some are 32bit and other are 64bit, and we go on forever providing differences but you get the picture…

Will begin with introducing some building blocks, and finally in the 2^nd part of this tutorial I will present the reader with tools (notations) that will help describe an algorithm regardless of the technologies used.

Let’s look at a simple while loop statement and describe it mathematically:

 

Figure 1, simple while loop that prints 99, “Whats up” statements
Ok, here is our complexity analysis of Figure 1, step by step:

1)      There is a variable declaration is int counter therefore, 1 constant operation

2)      “int counte”r is initialized to 0, 1 constant operation

3)      A logical operation is being performed 100 times, “while (counter<100)” , 100 operations

4)      System.out.println(“Whats up”), is printed 99 times, 99 operations

5)      “Counter” increase Counter by 1, 100 operations

6)       “Counter” is assigned new value or iterated, 100 operations

More or less according the steps above the code in figure 1 has complexity:

1 constant operation + 1 constant operation + 100 operations + 99 operations + 100 operations + 100 operations = 401 operations

Now if we thought of the expression “while (counter<100)” as “while (counter<n)”, in order to make a more general case, then:

1 constant operation + 1 constant operation + n operations + (n-1) operations + n operations + n operations = 3n+(n-1)+2  operations

You see the constants stay the same, and the while loop actually defines this algorithm

Therefore the above algorithms functions is f(n)=3n+(n-1)+2, this is a linear function

We are going to further simplify by using the following simple rules (Dasgupta, , and et al )):

1)      Multiplicative constants can be omitted,

Example 50n² simplifies to n²

2)      n^a dominates n^b if a>b

Example n³ dominates n², so n³ + n² + n ,simplifies to n³

3)      Any exponential dominates any polynomial

Example 3ⁿ dominates n⁵

Example 2ⁿ dominates 5n+100

4)      Any polynomial dominates any logarithm

Example n dominates  (log n)³

So if we applied rule #1 “Multiplicative constants can be omitted ” our analysis of Figure #1 , the function f(n)=3n+(n+1)+2, would simplify to f(n)=n.  This means the code in Figure #1 , behaves linearly.

Questions & Answers

Look at the following functions, what is the dominating feature or term in each function
(Hint: use the rules defined above)

1)      f(x)=x²+4x+30  

Answer = X²       , Using rules 1 & 2

2)      f(x)= x log x + 100x

Answer = X         ,Using rule 4

3)      f(x) = x⁵+x³+ log x + 30x

Answer = x⁵        ,Using rule 2 & 3

4)      f(x) = x²/30x      

Answer = X²           ,Using rule 3

5)      f(x) = x^3/2+x^1/3+x

Answer = x^3/2,    ,Using rule 3

Now 2 more examples and part 1 is finished.

 

Figure 2, For loop that iterates 10 times, and prints i’s value 10 times

Now that we know a “While loops” number of operations can be described as linear, we can apply that to any loop such as a “For” loop. Figure #2  is f(n)=n , or linear number if operations.

Figure 3, Inner loop is nested in outer loop , printing k’s value 10 times per each i’s iteration, therefore 100 print statements.

Nesting loops is just like multiplying the loops operations ,therefore one loop nested in another loop, performs n*n or n² operations, of course ignoring the minute constants.

Now let’s look at rates of growth before ending Part 1.

Rates of growth in order

Log₂ n < n < n log₂ n < n² < n³ < 2ⁿ

^{The above chained expressions summarize from the least to greatest, the mathematical features that most algorithms exhibit in terms of the runtime and input "n".}

^{Below is the graphical representation of the above expressions.}

(http://blog.philenotfound.com/2011/12/brief-intro-to-algorithmic-time.html)

By now we have learned very simple yet powerful simplification rules, for analyzing an algorithm’s time complexity, but in order to be more precise we need some formal notations

References

1.       2000 Solved Problems In Discrete Mathematics. 1st. New York: McGraw-Hill, 1992. 101-110. Print.

2.       Dasgupta, Sanjoy, First , et al. Algorithms. 1. Crawfordsville, IN: McGraw-Hill, 2008. Print.

3.    http://blog.philenotfound.com/2011/12/brief-intro-to-algorithmic-time.html

Basics: Factorial, Fibonacci, Algorithm, and Recursion

Basics: Factorial, Fibonacci, Algorithm, and Recursion

Our 1^st tutorial will focus on introductory mathematical functions in computer science & implementations.

J So let’s begin learning and don’t look back…

I’m sure everyone has heard of the factorial function by now which is denoted by,  n!

Definition # 1:

n! read “n factorial ,which in means “The product of the positive integers from 1 to N, inclusive…”  

("2000 Solved Problems In Discrete Mathematics" 101-110).

Side note: I copied this nice mathematical representation from Wikipedia. If I can’t find a nice graphical representation online than I will write in myself.

Examples & Questions:

5! = 5 * 4 * 3 * 2 * 1 = 120

10! = 10 * 9* 8* ….. * 1 = 3,628,800

The above definition states that for n=0 , the factorial function will return 1.

Therefore 0! =1.

And for n > 0 , then n multiplied by (n-1), recursively.

We will describe recursion soon in detail, it’s a very simple concept.

Definition # 2

Recursion is a function that calls or refers to itself.

Definition #3

Algorithm is a procedure for solving a mathematical problem (www.merriam-webster.com).

The word Algorithm is Latin name for Persian Arab mathematician Al-Khuwarizmi, who lived in ancient Persia, precisely modern day Iraq, he is also the founding father of Algebra. Algebra is also another Arabic word.

(http://www.encyclopedia.com/doc/1G2-2830902300.html).

Applications

Common use of factorials are in combinatorial analysis , such as combinations, permutations, binomial probability, etc.

Implementations in Java

The above implementation of the factorial function is based on the recursive definition, it is correct however naive, recursive functions tend to inefficient because they require previous recursive steps to be kept in memory and recalculated.  

The above implementation is an attempt at a more efficient “Algorithm”,however it is still recursive in nature because its needs to keep in “current memory” the previous step in order to compute current step.

This implementation is actually more efficient than previous recursive implementations. This time the previous factorial steps (j-1) are stored in array, and the current factorial is calculated by just accessing the results [j] = results[j-1] * j.

Now let’s go ahead and formally give definition for recursion.

Formal Definition of Recursion

A function is said to be recursive

1)      If there are certain base values, for which the function does not refer to itself.

2)      Every time the function refers to itself, the argument of the function must be closer to base value.

("2000 Solved Problems In Discrete Mathematics" 101-110).

You can easily see that the factorial function in definition # 1 , conforms to the formal definition above.

Now, run any of the implementations above for n!=5,n!=10,n!=50, you can see that factorial functions grows very fast , exponentially.

Now let’s look at another popular function, the Fibonnaci Sequence

0,1,1,2,3,5,8,13,21,34,55,89,…

Definition #4 , Fibonnaci Sequence

If n =0  or n =1, then F_n = n.

If  n> 1, then F_n = F_n-2 + F_n-1

("2000 Solved Problems In Discrete Mathematics" 101-110).

Applications

Fibonacci sequence is witnessed in the natural world, such as braches of a tree and petals of some flowers, it used to model some biological growth.

Examples & Questions:

1)      What is 10^th number in the Fibonacci sequence ?  fib(10) = 34

2)      What is the 20^th Fibonacci sequence , or fib(20)? Well don’t tell you are going add 20 numbers together by hand, let’s solve this by implementing the Fibonacci sequences definition.

Solution & Implementation in Java

The above Java code is recursive method that computes the Fibonacci sequence.

The above code is the loop that controls term we want the computation to terminate. The variable “n” below determines what Fibonacci term you want calculated.

Fibonacci 20, is computed as 6765 by above method called fib().

3)      What is the 200^th Fibonacci sequence?  Plug in 200 in the implementation from Question 2 and see what happens? It looks like recursive implementation was “Algorithmically inefficient”, so let’s re-implement Fibonacci using iterative approach.

Solution & Implementation in Java

J I’ll bet you any amount, that with above implementation you will not be able to calculate even Fibonacci 50.

So what’s happening? Isn’t the Java code the correct implementation of the Fibonacci definition? YES, but it’s “not an efficient implementation”, many mathematical formulas although correct, maybe inefficient if implemented directly based on their definition alone.

This is where the field of Algorithm Analysis & Computer Science becomes paramount, by providing alternative Algorithms/formulas that can be used in compute real world problems.

I have mentioned the word “efficient” several times, however so far I have not defined the “efficiency” formally, we will do so shortly.

For now just think of inefficient Algorithms, as functions that don’t have enough power to return desired answers in reasonable amounts of time.

A more efficient Implementation Fibonacci implementation

Fibonacci 200 is returned a this huge number 4,845,216,997,073,187,469 in under 1 second!!!.

J Can we do even better?  YES, we will visit this problem later when, we have built more mathematical & computational muscle.

Side note: Don’t dismiss recursion as inefficient technique; recursion is a powerful mathematical tool; many problems are solved recursively.

So far we learned about some functions, learned al little about recursion, and implemented our Algorithms.

However, to proceed we need to provide more formal definitions “efficiency”, and mathematical techniques to compare Algorithms.

Our next tutorial will be about, “Rate of growth…”.

 Further self-practice

1)      Implement a recursive method/function that doubles its input k, n times

2)      Implement a method/function that graphically prints out Khawrazmi’s Triangle (a.ka. Pascal’s Triangle)

3)      Implement Ackermann function recursively

References

1.       2000 Solved Problems In Discrete Mathematics. 1st. New York: McGraw-Hill, 1992. 101-110. Print.

2.       A Primer on Recursion. http://amitksaha.wordpress.com.

3.       Cormen, Thomas, et al. Introduction To Algorithms. 2nd. MIT press, 2001.