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