Simplification help with logarithms

8abylon

New member
Joined
Aug 5, 2018
Messages
2
Hi, I'm a bit rusty and was hoping someone could check my working to make sure I haven't strayed off the reservation.

For context, this is coming from simplifying the expression:

8^i T(n/2^i) + n^3(4^(i-1))

where i = log(2) n

Can I do this?:

4^((log(2) n ) - 1)
= 4 ^ log(2) n / 4
= n ^ log(2) 4 / 4 ****corrected for missing 4
= n^2 / 4

If not, how would I go about simplifying?
 
Last edited:
… For context, this is coming from simplifying the expression:

8^i T(n/2^i) + n^3(4^(i-1))

where i = log(2) n
After substituting for i, does the expression look like this?

\(\displaystyle \displaystyle 8^{log(2) \cdot n} \cdot T \cdot \frac{n}{2^{log(2) \cdot n}} + n^{3} \cdot 4^{log(2) \cdot n - 1}\)


Can I do this?:

4^((log(2) n ) - 1)
= 4 ^ log(2) n / 4
= n ^ log(2) 4
= n^2 / 4
No, I don't think so, but I think we can get rid of the log expressions in the other part.

Are you using log() to denote the base-10 logarithm?

Also, I have assumed that symbol T represents a number. If T is a function name, instead, we need to know.

Can you post the entire exercise statement, including the instructions? :cool:

Here is a link to the forum guidelines and a summary.
 
After substituting for i, does the expression look like this?

\(\displaystyle \displaystyle 8^{log(2) \cdot n} \cdot T \cdot \frac{n}{2^{log(2) \cdot n}} + n^{3} \cdot 4^{log(2) \cdot n - 1}\)


No, I don't think so, but I think we can get rid of the log expressions in the other part.

Are you using log() to denote the base-10 logarithm?

Also, I have assumed that symbol T represents a number. If T is a function name, instead, we need to know.

Can you post the entire exercise statement, including the instructions? :cool:

Here is a link to the forum guidelines and a summary.

Thanks for your response, to answer your questions:
  • Yes, after substituting for i that is the expression, with the clarification that the final 4 should be to the power of (log(2) n) - 1 and not log(2) (n-1)
  • I'm using log(2) n to denote the base-2 logarithm of n
  • T represents a function of time for a problem of size n, but will simplify to the number one on substituting i (as it becomes constant time)
  • I can post the exercise statement, but it is a bit disconnected from the problem of algebraic simplification (i.e. use the substitution method to find an asymptotic upper bound for the recurrence relation T(n) = 1 if n=1, T(n) = 8T(n/2) + n ^3 if n > 1).
 
  • Yes, after substituting for i that is the expression …
  • I'm using log(2) n to denote the base-2 logarithm of n
Knowing the base helps. I was looking at log(2)n as a product because I use function notation for functions.

We type an underscore or use brackets, to show other bases, and the function argument goes inside grouping symbols. Like this:

4^(log_2(n) - 1)

or

4^(log[2](n) - 1)

Or, you can define your own symbol at the beginning:

Log() = base-2 logs

or

log2(n) = log base-2 of n


… T represents a function of time for a problem of size n, but will simplify to the number one on substituting i …
Then my expression T ∙ (n/2^i) is not correct.

The expression is actually T(n/2^i), and, because this output of function T is 1, we can begin the simplification by deleting T(n/2^i) from the original expression, yes?

Function notation takes the form: name(input), like f(x).




Can I do this?:

4^((log(2) n ) - 1)
= 4 ^ log(2) n / 4
= n ^ log(2) 4 / 4
= n^2 / 4
Yes, n^2/4 matches what I got, although I didn't use that shortcut. :cool:
 
Last edited:
Top