MHB Solving T(n) = O(n lg n) using substitution method?

  • Thread starter Thread starter evinda
  • Start date Start date
AI Thread Summary
The discussion revolves around solving the recursive relation T(n) = 2T(⌊n/2⌋ + 17) + n and demonstrating that its solution is O(n log n). The initial assumption is that T(n) = O(n log n), leading to an analysis that reveals contradictions when applying the substitution method. The presence of the "+17" complicates the application of the Master theorem, suggesting the need for the Akra-Bazzi method, which is more advanced. Participants express concerns about the validity of their approach and the methods they are expected to use in their coursework. The conversation highlights the challenges of proving the complexity of this recursive relation.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! :-)

I am looking at the following exercise:
Show that the solution of the recursive relation $T(n)=2T( \lfloor \frac{n}{2} \rfloor +17)+n$ is $O(n \lg{n})$.

So,we suppose that $T(n)=O(n \lg n)$.

In order the recursive relation to be well-defined,I thought to use the inequality $\lfloor x \rfloor \geq x-1$ and I found:

$$ \lfloor \frac{n}{2} \rfloor+17 \leq n \Rightarrow n \geq \lfloor \frac{n}{2} \rfloor +17> \frac{n}{2}-1+17 \Rightarrow n>\frac{n}{2}+16 \Rightarrow n\geq 33$$

$$\text{ So, } n_0=33$$

As $T(n)=O(n \lg n)$,we suppose that $\exists c,b>0 \text{ such that } \forall n \geq 33 : T(n) \leq c(n-b) \lg n$We suppose that the relation stands also for $\lfloor \frac{n}{2} \rfloor+17$,then: $T(\lfloor{\frac{n}{2}} \rfloor+17) \leq c(\lfloor \frac{n}{2} \rfloor +17-b) \lg (\lfloor \frac{n}{2} \rfloor+17)$

$$T(n)\leq 2c(\lfloor \frac{n}{2} \rfloor+17-b) \lg ( \lfloor \frac{n}{2} \rfloor +17)+n \leq 2c (\frac{n}{2}+17-b) \lg n+n = c(n-b+(34-b)) \lg n +n \leq c(n-b) \lg n +n,\text{ if } 34 \leq b$$

We also know that it must be $ T(n)\geq 0 \Rightarrow n \geq b \Rightarrow b\leq n, \forall n \geq n_0 \Rightarrow b\leq n_0 \Rightarrow b \leq 33$

So,we have a contradiction..Also,even if it was not a contadiction,we couldn't do it in this way,because: $c(n-b) \lg n +n \geq c(n-b) \lg n$

But..how can we show it then? (Thinking)
 
Last edited:
Technology news on Phys.org
evinda said:
I am looking at the following exercise:
Show that the solution of the recursive relation $T(n)=2T( \lfloor \frac{n}{2} \rfloor +17)+n$ is $O(n \lg{n})$.

So,we suppose that $T(n)=O(n \lg n)$.
Do you always assume what you need to show?

evinda said:
As $T(n)=O(n \lg n)$,we suppose that $\exists c,b>0 \text{ such that } \forall n \geq 33 : T(n) \leq c(n-b) \lg n$
Why not $T(n) \leq cn\lg n$?

This problem would be covered by the master theorem (case 2) if it were not for $+17$. It is covered by the Akra–Bazzi method, which is a generalization of the master theorem. In the notations of the Wiki page, $g(x)=x$, $k=1$, $a=2$, $b=1/2$ and $h(x)=17+\lfloor n/2\rfloor-n/2$. However, this theorem is more advanced and may not be covered in some courses dealing with recurrence relations.

What is the context of this problem? Where in the course or book are you? What methods are you supposed to solve it?
 
Evgeny.Makarov said:
Do you always assume what you need to show?

I saw at the solution of a similar exercise that they did it like that.. So is it wrong? (Thinking)(Worried)

Evgeny.Makarov said:
Why not $T(n) \leq cn\lg n$?

I have also tried it,supposing $T(n) \leq cn\lg n$,then I supposed that the relation also stands for $\lfloor \frac{n}{2} \rfloor +17: T(\frac{n}{2} \rfloor +17) \leq c( \lfloor \frac{n}{2} \rfloor +17) \lg (\lfloor \frac{n}{2} \rfloor+17)$

So:

$$T(n) \leq 2c(\lfloor \frac{n}{2} \rfloor+17) \lg (\lfloor \frac{n}{2} \rfloor+17)+n \leq 2c(\lfloor \frac{n}{2} \rfloor+17) \lg n+n \leq 2c(\frac{n}{2}+17) \lg n+n \leq c(n+34) \lg n +n$$
Evgeny.Makarov said:
This problem would be covered by the master theorem (case 2) if it were not for $+17$. It is covered by the Akra–Bazzi method, which is a generalization of the master theorem. In the notations of the Wiki page, $g(x)=x$, $k=1$, $a=2$, $b=1/2$ and $h(x)=17+\lfloor n/2\rfloor-n/2$. However, this theorem is more advanced and may not be covered in some courses dealing with recurrence relations.

What is the context of this problem? Where in the course or book are you? What methods are you supposed to solve it?

I haven't seen the Master theorem yet..I am supposed to solve it,using the substitution method.. (Worried)
 
Thread 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
I tried a web search "the loss of programming ", and found an article saying that all aspects of writing, developing, and testing software programs will one day all be handled through artificial intelligence. One must wonder then, who is responsible. WHO is responsible for any problems, bugs, deficiencies, or whatever malfunctions which the programs make their users endure? Things may work wrong however the "wrong" happens. AI needs to fix the problems for the users. Any way to...

Similar threads

Replies
1
Views
2K
Replies
8
Views
2K
Replies
15
Views
3K
Replies
7
Views
2K
Replies
9
Views
2K
Back
Top