[ACE] Recurrence Relation

Recurrence Relation

Acknowledgement

The following content is summarized by G52ACE class and MIT open source course(Introduction to Algorithms).

Main Body

We don’t care the official definition of recurrence relation, but we need to know:
Suppose that the runtime of a program is T(n), then a recurrence relation will express T(n) in terms of its values at other (smaller) values of n.
Example:
Suppose the runtime of merge-sort of an array of n integers is T(n). Then T(n) = 2 T(n/2) + b + a n:
enter image description here
• “2 T(n/2)” is due to having to sort the two sub-arrays each of size n/2
• “b” is the cost of doing the split
• “a n” is the cost of doing the merge (and any copying to/from the workspace, etc.)
Also, what is our base case? ===> T(1) = 1
Thus, how can we solve this recurrence relation?

Solving Recurrence using induction(introduced by G52ACE course)

General pattern
1. Starting from the base case, use the recurrence to work out many cases, by directly substituting and working upwards in values of n
2. Inspect the results, look for a pattern and make a hypothesis for the general results
3. Attempt to prove the hypothesis – typically using some form of induction
enter image description here
If we regard 2^k to n
T(n) = n + n * log n * a +(n-1) * b = O(n log n)
Often then extract the large n behavior using big-Oh family

Solving Recurrence using Recurrence Tree(introduced by Book)

First we should cast the formula to this

Put the θ(n) to cn then we can draw a recursion tree
What we need to do is to figure out how many leaves are in the lowest level, what is the height of the tree and what is the total of each level

Because the height is logn, the total of each level is cn for internal leaves and θ(n) for external leaves.
Thus, the total is (cn) * lgn + θ(n), we ignore θ(n), it is θ(n log n)

There is not a usual way to solving recurrence, so in terms of different question, we should use different method, here are two other important method– Substitution method and Master Theorem

Substitution method

First, guess the form of solution
Second, verify by induction
Third, solve the constant
It is somehow similar to the method we learned in the class and i need to further check with my tutor.
But i’d like to introduce this method here:
Here is a example:

In my opinion, it is similar to the method we learned before but it is not so precise. It just can work out O(n^3) in this example but it is not Θ(n^3) because it is O(n^2) in this example too. So it just can narrow your assumption down to some range but not exact complexity.

The master theorem(Both introduced by lecture and book)

MT applies to
T(n) = a T(n/b) + f(n) where a>=1, b>1, f(n) is asymptotically positive
  • what does it mean by “asymptotically positive”?
  • It is when n is bigger enough, f(n) should be positive===> f(n) > 0 for n>= 0;
Results are split into 3 cases, according to comparing the growth rate of f(n) to n^ (log b a)
There are a lot of similar format of MT but i pick the one on Wikipedia
- Case 1:
enter image description here
- Case 2:
enter image description here
- Case 3:
enter image description here
Keep in mind that there are a lot of situation that MT can not applies to.
Here are two examples solving actually question in MT(Binary Search and Merge Sort)
enter image description here

So how to prove MT? why f(n) should be compared to n ^ (log b a)?

The prove in Introduction to Algorithm is using tree, but i tried to prove it using mathematical expressions:
enter image description here
Here we can see we work out n ^ (log b a), and each case, what we do is to compare it to see which is the dominance of the expression
Okay, it is just my opinion, let’s see how it should be proved officially
enter image description here
We are using a recursive tree.
If we add the total work of the tree, what we will get?!
Cool! Its what i proved above in the last equation!
n ^ (log b a) is the sum of the leaves at the bottom
The above sum of each level will be showed as the summation formula!
It is the same as induction by mathematic
In Case 1: the weight or dominance is on the external leaves than the roots(and internal leaves), so we should use the sum of leaves which is n ^ (log b a)
In Case 2: the weight is similar between them so we should add them up
In Case 3: the weight is mostly on the internal leaves so we should ignore external leaves and it should be O( f(n) )

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If
阅读全文

[AIM] MetaHeuristics

图片
Day2 Outline Metaheuristics -definition Single point based search method(simple stochastic local search) Iterated local search Scheduling Tabu Search Metaheuristic what is a metaheuristic? A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. what is the difference between heuristic and metaheuristic? Heuristic : Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution. Metaheuristic : Meta-heuristics, on the other hand, are problem-independent techniques . As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes . In general, t
阅读全文