• Support PF! Buy your school textbooks, materials and every day products Here!

Proof with recursion and logarithms

  • #1

Homework Statement:

Suppose f(n) is a function that accepts an integer n as a parameter. When called with n = 1, it executes 2 instructions. When called with a larger value of n, it executes 10n + 30 instructions, two of which are f(n/2). Prove that f(n) executes 10n lg n + 32n − 30 instructions for all n ≥ 1.

lg = log base 2. Hint: a useful property of logs is that lg(a/b) = lg(a) - lg(b) for any non-zero a,b

Relevant Equations:

...
Homework Statement: Suppose f(n) is a function that accepts an integer n as a parameter. When called with n = 1, it executes 2 instructions. When called with a larger value of n, it executes 10n + 30 instructions, two of which are f(n/2). Prove that f(n) executes 10n lg n + 32n − 30 instructions for all n ≥ 1.

lg = log base 2. Hint: a useful property of logs is that lg(a/b) = lg(a) - lg(b) for any non-zero a,b
Homework Equations: ...

This is how far I get:

let n = k+1

instructions for f(k+1) = 10(k+1) + 30 + 10(k+1)/2 + 30 + 10(k+1)/2 + 30
= 10k + 10 + 30 + (10k+10)/2 + 30 + (10k+10)/2 + 30
= 10k + 10 + 30 + 10k + 10 + 30 + 30
then rearranging we get = (10k + 30) + (10K + 30) + 10 + 10 + 30
from inductive step we know (10k + 30) = (10k⋅lgk + 32k - 30) therefore
= (10k⋅lgk + 32k - 30) + (10k⋅lgk + 32k - 30) + 10 + 10 + 30

I get stuck at this point :frown:
 

Answers and Replies

  • #2
tnich
Homework Helper
1,048
336
I think proof by induction will work, but you will need to figure out the right induction hypothesis. Specifically, you will need to show what the value of ##f(n)## is in step ##k+1## given that you know ##f(n/2)## in step ##k##. How would you express ##n_k## for ##k\in \mathbb Z^+##?

By the way, the problem statement is incomplete in that it does not tell you what happens when ##n/2## in not an integer. The number of instructions in the case is undefined. Is there a definition that is consistent with the desired result?
 
Last edited:
  • #3
I think proof by induction will work, but you will need to figure out the right induction hypothesis. Specifically, you will need to show what the value of ##f(n)## is in step ##k+1## given that you know ##f(n/2)## in step ##k##. How would you express ##n_k## for ##k\in \mathbb Z^+##?

By the way, the problem statement is incomplete in that it does not tell you what happens when ##n/2## in not an integer. The number of instructions in the case is undefined. Is there a definition that is consistent with the desired result?
Unfortunately it makes no mention what happens when n/2 is not an integer. Which is confusing me because the first sentence of the problem states that f(n) "accepts an integer n as a parameter" yet it has 2 recursive calls of n/2.
 
  • #4
33,631
5,288
Unfortunately it makes no mention what happens when n/2 is not an integer. Which is confusing me because the first sentence of the problem states that f(n) "accepts an integer n as a parameter" yet it has 2 recursive calls of n/2.
My sense is that this is a "computer sciencey" type question. If so, one might interpret n/2 to mean integer division -- i.e., the result is an integer. For example, 4/2 == 2, but also 5/2 == 2 when integer division is used.
 
  • #5
My sense is that this is a "computer sciencey" type question. If so, one might interpret n/2 to mean integer division -- i.e., the result is an integer. For example, 4/2 == 2, but also 5/2 == 2 when integer division is used.
I sent an e-mail to my TA I'm waiting for a response. Also, I apologize if this is not considered the correct forum I was stuck between this one and the Engineering forum.
 
  • #6
33,631
5,288
Also, I apologize if this is not considered the correct forum I was stuck between this one and the Engineering forum.
Not a problem -- I moved your thread for you, assuming that this is more of a computer science question.

Before attempting an induction proof, as was earlier suggested, what I would do is make a small table of instruction counts for n = 2, n = 3, n = 4, to see if you can see a pattern developing.
 
  • Like
Likes enigmatic01
  • #7
tnich
Homework Helper
1,048
336
Unfortunately it makes no mention what happens when n/2 is not an integer. Which is confusing me because the first sentence of the problem states that f(n) "accepts an integer n as a parameter" yet it has 2 recursive calls of n/2.
I have tried the given formula and found that it works for ##n## a power of 2.

As @Mark44 says, this is a computer science question, so you might think of the given formula as a big O complexity bound, define ##f(n) = 0## for odd ##n>1## or as @Mark44 suggests, use integer division, and go from there.

I think you still need to build your proof by induction so that the induction step looks like:

"##f(n) = 10n \log_2 n +32n-30## implies that ##f(2n) = 10(2n) \log_2 (2n) +32(2n)-30##. "

What function of ##k\in \mathbb Z^+## could you substitute for ##n## to make this look like the standard induction step?
 
  • #8
I have tried the given formula and found that it works for ##n## a power of 2.

As @Mark44 says, this is a computer science question, so you might think of the given formula as a big O complexity bound, define ##f(n) = 0## for odd ##n>1## or as @Mark44 suggests, use integer division, and go from there.

I think you still need to build your proof by induction so that the induction step looks like:

"##f(n) = 10n \log_2 n +32n-30## implies that ##f(2n) = 10(2n) \log_2 (2n) +32(2n)-30##. "
ƒ
What function of ##k\in \mathbb Z^+## could you substitute for ##n## to make this look like the standard induction step?
Thank you for your help. Do you mean setting n = k + 1 then substituting that in to the f(2n) equation?
 
  • #9
If anyone cares I figured it out (with help)...

After proving base case of f(1) we assume function holds true for all n up to k (strong induction). Consider k+1.

f(k+1) = 10(k+1) + 30 + 2*f( (k+1) /2) since k is > 1 we know (k+1)/2 is less than k

= 10(k+1) + 30 + 2[ 10( (k+1) /2 )*lg( (k+1) / 2) + 32( (k+1) / 2) - 30 ]

after skipping some algebra...

= 10(k + 1) [ 1 + lg( (k + 1) / 2) ] + 32(k + 1) - 30

= 10(k + 1) [ 1 + lg(k + 1) - lg(2) ] + 32(k + 1) - 30

= 10(k + 1)[1+ lg(k + 1) - 1 ] + 32(k + 1) - 30

= 10(k + 1)lg(k + 1) + 32(k + 1) - 30
 
  • #10
tnich
Homework Helper
1,048
336
If anyone cares I figured it out (with help)...

After proving base case of f(1) we assume function holds true for all n up to k (strong induction). Consider k+1.

f(k+1) = 10(k+1) + 30 + 2*f( (k+1) /2) since k is > 1 we know (k+1)/2 is less than k

= 10(k+1) + 30 + 2[ 10( (k+1) /2 )*lg( (k+1) / 2) + 32( (k+1) / 2) - 30 ]

after skipping some algebra...

= 10(k + 1) [ 1 + lg( (k + 1) / 2) ] + 32(k + 1) - 30

= 10(k + 1) [ 1 + lg(k + 1) - lg(2) ] + 32(k + 1) - 30

= 10(k + 1)[1+ lg(k + 1) - 1 ] + 32(k + 1) - 30

= 10(k + 1)lg(k + 1) + 32(k + 1) - 30
There is a hidden assumption in your proof - that ##f(n)## is defined for ##n## not an integer. Aside from that it works, but if I were grading your homework, I would take some points off for that. However, I would give you some credit if you showed that you at least knew you were making that assumption, for example, if you stated what you assumed to be the number of operations when ##n## is not an integer.

Still, I think the issue is really in the problem statement, since as stated it is not true except for ##n## a power of 2.
 
  • Like
Likes enigmatic01
  • #11
There is a hidden assumption in your proof - that ##f(n)## is defined for ##n## not an integer. Aside from that it works, but if I were grading your homework, I would take some points off for that. However, I would give you some credit if you showed that you at least knew you were making that assumption, for example, if you stated what you assumed to be the number of operations when ##n## is not an integer.

Still, I think the issue is really in the problem statement, since as stated it is not true except for ##n## a power of 2.
I sent an e-mail to my TA for clarification but I have not heard back yet. Any suggestions on how I should address it if I don't hear back?
 
  • #12
tnich
Homework Helper
1,048
336
I sent an e-mail to my TA for clarification but I have not heard back yet. Any suggestions on how I should address it if I don't hear back?
You could give a counter example that shows the formula does not work. Show that the number of operations for ##n=3## is undefined.

Then you could give your proof and explain what you would have to assume about the number of operations for ##f(n)## when ##n## is not an integer to make the proof work. Is it zero? Is it ##10n + 30##? Is it ##10n + 30 + 2[\text {number of operations for } f(n/2)]##? Is it ##10n \,lg\,n + 32n -30##?

One question: did you state the problem in the original post exactly as it was given to you, or did you paraphrase it?
 

Related Threads on Proof with recursion and logarithms

  • Last Post
Replies
1
Views
832
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
16
Views
9K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
15
Views
1K
Replies
1
Views
4K
Replies
0
Views
5K
  • Last Post
Replies
4
Views
196
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
9
Views
4K
Top