Proving a[n] = Θ(lg n): A Case Study

  • Thread starter Thread starter e(ho0n3
  • Start date Start date
  • Tags Tags
    Study
AI Thread Summary
The discussion focuses on proving that the sequence a[n] is Θ(lg n) under the condition that a[n] is an increasing sequence where a[n] = a[n/m] + d for any divisor m of n. Participants explore the relationship between a[n] and logarithmic growth, with one member successfully demonstrating that a[n] is O(lg n). The challenge remains to establish that a[n] is also Ω(lg n), which is crucial for the Θ notation. Concerns are raised about the implications of the proof when n is odd, highlighting the need for clarity in the reasoning. The conversation reflects a collaborative effort to resolve the proof's complexities.
e(ho0n3
Messages
1,349
Reaction score
0
a[n] = Θ(lg n)!?

Suppose {a[n]} is an increasing sequence and whenever m divides n, then

a[n] = a[n/m] + d

where m is a positive integer and d is a real number. Show that a[n] = Θ(lg n).

a[n/m] + d ≤ a[n/2] + d, and with this I can show that a[n] = O(lg n). All I need to do is show that a[n] = Ω(lg n). This is where I'm stuck. Any hints?
 
Mathematics news on Phys.org
To show that something is in omega(log x), it suffices to find some sequence {x_i} such that a[x_i] grows like log x.

By the way, I'm disconcerted with your reasoning that it is in O(log x); what if n is odd? I suppose you're just abbreviating the complete proof you have.
 
Hurkyl said:
By the way, I'm disconcerted with your reasoning that it is in O(log x); what if n is odd? I suppose you're just abbreviating the complete proof you have.
Sorry. What I meant was

a_n = a_{\lfloor n/2 \rfloor} + d

My head is a total blank. I can't think of anything.
 

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »

Thread 'Non-orthogonal bases'

Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
View full post »
Thread 'Imaginary Pythagoras'

Thread 'Imaginary Pythagoras'

I posted this in the Lame Math thread, but it's got me thinking. Is there any validity to this? Or is it really just a mathematical trick? Naively, I see that i2 + plus 12 does equal zero2. But does this have a meaning? I know one can treat the imaginary number line as just another axis like the reals, but does that mean this does represent a triangle in the complex plane with a hypotenuse of length zero? Ibix offered a rendering of the diagram using what I assume is matrix* notation...
View full post »

Similar threads

Prove recurrence relation via mathematical induction
Replies
5
Views
1K
MHB What is the remainder when m+n is divided by 1000 in a trigonometric challenge?
Replies
2
Views
1K
I Questions regarding Kurepa's Conjecture
Replies
1
Views
2K
A How Does U(1) Double-Cover SO(2) for a Specified Angle?
Replies
2
Views
2K
MHB Digit sum rule for the divisibility by 9
Replies
2
Views
2K
I Optimization problem with multiple outputs: impossible?
Replies
6
Views
2K
MHB Is There an Easier Method to Prove $n^2>n$ for Negative Integers?
Replies
2
Views
2K
I Are there any two pairs of integers with the same result in a specific function?
Replies
7
Views
2K
MHB Proving $T(n)=O(n^2 \lg^2 n)$ Using Recurrence Relation
Replies
2
Views
2K
Complexity of this heap algorithm
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top