Understanding Logarithms: Solving Recurrence Relations Explained | O(n log n)

  • Thread starter theintarnets
  • Start date
  • Tags
    Logarithms
In summary, the conversation discusses a recurrence relation and the equivalent forms of 2(log2 n) + kn = n + log2 n * n. The rest of the relation is shown to understand how those two lines became equivalent. It is also mentioned that raising 2 to the logarithm of n will resolve the function 2^n. The definition of a logarithm is also mentioned in relation to the content.
  • #1
theintarnets
64
0
I'm having trouble understanding the last two lines of a recurrence relation:

2(log2 n) + kn
= n + log2 n * n

I get the rest of the recurrence relation, but I don't understand how those two became equivalent. Where did k go? Where did + n come from? and what happened to the 2?

Here is the rest of the relation in case it is needed to understand those two lines:
T(1) = 1

T(n) = T(n/2) + T(n/2) + n
= 2 T(n/2) + n

= 2 [2 T(n/4) + (n/2)] + n
= 4 T(n/4) + 2n

= 4 [2 T(n/8) + (n/4)] + 2n
= 8 T(n/8) + 3n

= ...
= 2^k T(n/(2^k)) + k n

Suppose (n/(2^k)) = 1:
Then, n = 2^k => k = log n

= 2^(log_2 n) * T(1) + k n
= 2^(log_2 n) * 1 + k n
= 2^(log_2 n) + k n
= n + (log_2 n) * n

=> O(n log n)
 
Physics news on Phys.org
  • #2
Where did k go? Where did + n come from? and what happened to the 2?

From the rest of the relation:
Suppose (n/(2^k)) = 1:
Then, n = 2^k => k = log n
 
  • #3
What value do I raise the constant "2" to, in order to resolve the function 2^n?

That is what 2^(log2 n) is saying.
 
  • #4
@theintarnets: sherrellbc has provided a good hint:
That is what 2^(log2 n) is saying.
i.e. what is the definition of the logarithm?

##a^b=c## then ##\log_a(c)=b## so if you do ##a^{\log_a(c)}## .. what do you get?
(Try it out using base 10.)
 
Last edited:
  • #5
Simon Bridge said:
You tell me: what is the definition of a logarithm?

I take it you understand "where the k went" now?

##a^b=c## then ##\log_a(c)=b## so if you do ##a^{\log_a(c)}## .. what do you get?
(Try it out using base 10.)

I was making a comment. I think you mistook me for the OP.
 
  • #6
I was making a comment. I think you mistook me for the OP.

Yes I did - my apologies :D
Edited.
 

Related to Understanding Logarithms: Solving Recurrence Relations Explained | O(n log n)

1. What is a logarithm?

A logarithm is a mathematical function that represents the power to which a base number must be raised to produce a given number. In other words, it is the inverse operation of exponentiation.

2. Why are logarithms useful?

Logarithms are useful because they allow us to simplify complex calculations involving large numbers. They also help to convert multiplication and division problems into simpler addition and subtraction problems.

3. How do I solve logarithmic equations?

To solve a logarithmic equation, you must isolate the logarithm on one side of the equation and the constant on the other side. Then, you can use the properties of logarithms to simplify the equation and solve for the variable.

4. What are the common properties of logarithms?

The properties of logarithms include the product property, quotient property, power property, and change of base property. These properties can be used to simplify logarithmic expressions and solve logarithmic equations.

5. Where can I find help with logarithms?

You can find help with logarithms from various online resources, such as math tutoring websites, instructional videos, and math forums. Your school or university may also offer tutoring services or have a math help center where you can get assistance with logarithms.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
3
Views
975
  • Precalculus Mathematics Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
10
Views
671
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
634
  • Precalculus Mathematics Homework Help
Replies
5
Views
1K
Back
Top