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

  • Context: Graduate 
  • Thread starter Thread starter e(ho0n3
  • Start date Start date
  • Tags Tags
    Study
Click For Summary
SUMMARY

The discussion centers on proving that the sequence {a[n]} defined by the recurrence relation a[n] = a[n/m] + d, where m divides n, satisfies the asymptotic notation a[n] = Θ(lg n). The participants establish that a[n] is O(lg n) by demonstrating that a[n/2] + d serves as an upper bound. The challenge lies in proving that a[n] is also Ω(lg n), which requires identifying a sequence {x_i} such that a[x_i] grows logarithmically. The conversation highlights the importance of addressing cases where n is odd and clarifies the recurrence relation as a_n = a_{\lfloor n/2 \rfloor} + d.

PREREQUISITES
  • Understanding of asymptotic notation (Θ, O, Ω)
  • Familiarity with recurrence relations in algorithm analysis
  • Knowledge of logarithmic growth rates
  • Basic principles of number theory regarding divisibility
NEXT STEPS
  • Study the Master Theorem for solving recurrences
  • Learn about logarithmic functions and their properties
  • Explore examples of sequences defined by recurrence relations
  • Investigate the implications of odd and even cases in algorithm analysis
USEFUL FOR

Mathematicians, computer scientists, and students studying algorithm analysis, particularly those interested in recurrence relations and asymptotic analysis.

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

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

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

Similar threads

Graduate About a natural extension of Collatz conjecture
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Proving Goldbach's conjecture by induction (or why it doesn't seem to work)
  • · Replies 10 ·
Replies
10
Views
4K
Graduate Prove recurrence relation via mathematical induction
  • · Replies 5 ·
Replies
5
Views
1K
MHB What is the remainder when m+n is divided by 1000 in a trigonometric challenge?
  • · Replies 2 ·
Replies
2
Views
2K
Graduate Prime Number Powers of Integers and Fermat's Last Theorem
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
3K
MHB Digit sum rule for the divisibility by 9
  • · Replies 2 ·
Replies
2
Views
2K
MHB Is There an Easier Method to Prove $n^2>n$ for Negative Integers?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Optimization problem with multiple outputs: impossible?
  • · Replies 6 ·
Replies
6
Views
3K
Undergrad Are there any two pairs of integers with the same result in a specific function?
  • · Replies 7 ·
Replies
7
Views
3K