Recent content by enigmatic01

That was actually the other homework problem!

Use the formal definition of Big-Oh to prove that if f (n) and g(n) are nonnegative functions such that f (n) = O(g(n)), f (n) + g(n) = Ω(g(n)). By the definition of Big-Oh: If f(n) and g(n) are non-negative functions such that f(n) = O(g(n)) there must be positive constants c and n0 such...

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?

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) /...

Thank you for your help. Do you mean setting n = k + 1 then substituting that into the f(2n) equation?

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.

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.

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...