Title: What does T(n) is constant for n < 2 mean in recurrences?
Tags: algorithm;graph-algorithm
Question: I am reading the book "Introduction to Algorithms" and I have this problem that is saying to derive the lower and upper bound for T(n) for the following recurrence :
T(n) = 36T(n/6) + 2n
And its saying assume that: T(n) is constant for n <= 2, can anyone explain to me the last sentence, what does that really mean?
assume that: T(n) is constant for n <= 2
Comment: Possibly that T(1) and T(2) is independent of n, I guess.

Here is the accepted answer: It means T(0) = c_0 and T(1) = c_1 are constant proportional to n to notify that you should not worry about them and compute them as a constant in time complexity. If they are not constant, as they are the basis of the recurrent equation, you can't use the master theorem to analyze the complexity.
Suppose in real n is in the order of 10^20, but T(0) = 10^50, and T(1) = 10^60. Hence, you can't compute the complexity using the master theorem.
Comment for this answer: Okay thank you but I have another question related to this, using the same assumtion I have to find also the T(n) = 12T(n/2) + n^2 * log n, so using the Generic Master Theorem I arrived at T(n) = O(n ^ 3.58496), should I leave the result just like this or does this mean that I have only found the upper bound O, if yes how should I find the lower bound Ω then?
Comment for this answer: I wonder if 'T(0) is not constant' has any meaning. Given that the only parameter to T is a constant 0, shouldn't T(0) must be a constant? Then the assumption is the question looks redundant.
Comment for this answer: yes but both  10^50 / 10^60 are actually very large constant?
Comment for this answer: Yes, in real world we need to take care of them. But I think this question is more about theoretical problem.
Comment for this answer: @Dan The upper bound is correct, in this way. For \Omega case, you can easily say `T(n) = \Omega(n^2 * log n)` as we have this part currently in the equation.
Comment for this answer: @PetarPetrovic Did you see my example?
Comment for this answer: @PetarPetrovic if `n` is in the order of `10^20`, so they are not! Indeed, in real situations I mean.
Comment for this answer: @PetarPetrovic If it is, it should be in TCS, not in SO. Anyhow, it is not, as the answer is accepted by the OP. And thanks for your comments.


{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 1, 'CommentCount': 1, 'ContentLicense': 'CC BY-SA 3.0', 'CreationDate': '2018:00:02/13/18', 'FavoriteCount': None, 'PostTypeId': 1, 'Tags': '<algorithm><graph-algorithm>', 'Title': 'What does T(n) is constant for n < 2 mean in recurrences?', 'ViewCount': 139, 'id': 48774808, 'user_AboutMe': '<p>Student in Belgium </p>\n\n<p>aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!</p>\n', 'user_AccountId': 12000899.0, 'user_DisplayName': 'Dan', 'user_Reputation': 139.0, 'user_Views': 68.0, 'user_id': 8858555.0}}