How to prove this:
- 4n = O(8n)
- 8n = O(4n)?
So what are the C and n0 values for both cases?
views:
350answers:
2
+2
A:
EDIT: I tried to clarify I bit more ...
1.
For a proof (see formal definition of Big-O) we have to find any C and n0, that 4n <= C * 8n for all n > n0.
So - to prove your case 1 it is all about finding an example for these two values. We will try ... the equation I just quoted from wikipedia says:
f(n) = O(g(n))
if and only if there exists a positive real number C and a real number n0 such that
|f(n)| <= C * |g(n)| for all n > n0
where f(n) = 4n and g(n)=8n
4^n <= C * 8^n
4^n <= C * 2^n * 4^n
1 <= C * 2^n
So we choose C to be 1 and n0 to be 1, too. The equation is true -> case 1 proven.
2.
Since I guess, that this is homework - you should give it a try yourself - I can help you a bit more, as soon as you provide results of your own tries.
Hint: just try to find a C and a n0 there, too - maybe you can prove, that there never exists any pair of C and n0 for the equation ... ^^
tanascius
2010-04-19 14:23:12
@downvoter: is the proof wrong or what's the problem here?
tanascius
2010-04-19 14:28:41
@downvoter: If you down vote, you must have different opinion huh? Can you try answer and let us discuss?@tanascius: Thanks for the answer for case1. Case 2, i get C 2 but n0 is XX? I dun understand how to get n0...
rachel7660
2010-04-19 14:53:41
@rachel: How did you get C==2? It should be something like `n^2 <= C` ...
tanascius
2010-04-19 14:56:04
(1)4^n <= C * 2^n * 4^nThus, 2 is the C(2) 2^n <= C
rachel7660
2010-04-19 15:15:01
But not sure if my answers are correct
rachel7660
2010-04-19 15:15:15
@rachel: I interpret your result as: *Whatever `C` you choose, there will be no `x0`, so that all `2^n` with n > x0 will be smaller than C.*
tanascius
2010-04-19 15:16:49
So, for case 2, its an invalid statement? How about case 1? C is 2, n0 = 0??
rachel7660
2010-04-19 15:27:08
@rachel: I case 2 there is no solution -> no proof -> statement incorrect. In case one we already found a solution for the equation (C=1, x0=1) -> proof -> statement correct.
tanascius
2010-04-19 15:52:34
Did you read and understand the formal definition of Big-O? *f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that ...*
tanascius
2010-04-19 15:53:24
!thinking!.... your answer...... sigh
rachel7660
2010-04-19 16:19:39
@rachel: I edited, please tell me whether you understand the proof for case 1, because we don't have to talk about case 2 as long as you don't understand what I wrote ...
tanascius
2010-04-19 16:33:33
@tan: Ok, lets forget the case2. I understand until this part: 1 <= C * 2^n. But I dunno how to prove, or find the value of C and n0. I think, u must be feel very pissed off of my stupidity. But trust me, I am really trying very hard to understand.
rachel7660
2010-04-19 16:38:45
@rachel: ok, the trick is that you don't calculate the values ... you just pick them as you like. Here is the equation: *1 <= C * 2^n* - and now I ask you: give values for C and n0 that this equation is true for C and all n >= n0 ... you just choose C to be one ... no reason given. So when is *1 <= 2^n*? Obviously for all n>=0 ... so you can choose any number > 0 for n0 and that's all: *1 <= 1 * 2^0*, *1 <= 1 * 2^1*, *1 <= 1 * 2^1*, *1 <= 1 * 2^2*, ... done
tanascius
2010-04-19 16:47:21
@tan: For case1, if C = 2, n0 = 1, it returns a true statement as well. So as for C =4,5,6 ..., Thus, can I say, c>=1, n0 = 1?
rachel7660
2010-04-19 16:48:53
It means that you were able to find a C and a n0 for this equation. And that is all that's needed ... *... if and only if there exists a positive real number C and a real number n0 such that ...* By finding two (randomly chosen or somehow selected) values you already provided the proof.
tanascius
2010-04-19 16:49:20
@rachel: For case 2 you are still looking for a fixed C and a n0 so that the equation *2^n <= C* is valid for **all n >= n0** ... You said C = 2 and n0 = 1 ... let's see, I pick an n >= you n0 which shall be 1000. Is 2^1000 <= 2? No it is not. Try to find another pair - and you won't find any pair - I am sure.
tanascius
2010-04-19 16:52:07
@tan: Now i get it. because C is a constant, so it will always same no. In this case, you chose 1, so 1 times any number of n0 thats > 0, will make the statement is true. Is that what you mean?
rachel7660
2010-04-19 16:52:32
Yes, it is important to understand that C is a constant, while n0 is only a lower bound ... I will not use n0 for a proof, but all numbers n >= n0 ...
tanascius
2010-04-19 16:54:42
@rachel: for case 2. Can a function going **downward** get higher than any fixed value greater than the initial one.
kriss
2010-04-19 16:55:41
@tan: I think, I finally undestand the concept. I have a big problem now, how should I thank you? I really want to meet and say millions of thank you thank you thank you........
rachel7660
2010-04-19 16:55:59
@rachel ... no problem, I am happy as long as this all lead to anything :)
tanascius
2010-04-19 16:57:23
@tan: I Love u ^_^. Oh ya, now I understand why you say case2 is invalid statement. I am so happy now :) :) :)
rachel7660
2010-04-19 16:57:46
@rachel: great ... that was my longest comment-based conversation on SO so far :) bye ^^
tanascius
2010-04-19 17:00:24
@tan: I have another question. But, I really feel that, I should not bug you anymore. Its about how to determine best case and worst case of a function. If you dont mind, can you give me about 5 more minutes? I need hint
rachel7660
2010-04-19 17:01:42
Maybe you want to ask a new question here on SO? You can post the link here as a comment - but don't expect me to answer really early - it is past 7pm and I am going home right now ... I will come back later this evening
tanascius
2010-04-19 17:04:05
Its 3 am here. I am still studying. Okay, I will post 2 more questions and the links here in comment sections. I will wait for ya. If I sleep, could you please add my yahoo email?
rachel7660
2010-04-19 17:09:51
Q(1):http://stackoverflow.com/questions/2669437/how-to-find-the-formula-of-best-case-and-worst-case-of-my-algorithm and Q(2):http://stackoverflow.com/questions/2669467/sorting-the-order-of-growth-of-the-functions
rachel7660
2010-04-19 17:25:30
+1
A:
From what I remember of the law of logarithms:
logb(xy) = (y)logb(x)
I think this is a good starting point. I'm not going to finish because this is a homework assignment. ;)
UPDATE:
The more I look at it, the more I think that something is missing from the original question. Define what C and n0 are, for starters.
FrustratedWithFormsDesigner
2010-04-19 14:58:01
Erm.. Still no clue about it. My answer for case 1: C = 2 N0 = dunno. Case 2: c>= 2^n N0 also dunno. Is that correct?
rachel7660
2010-04-19 15:16:23
I already tried my best, please help me? I want to study, thats why I ask this question. If I dont care about my school, I wont be asking here and probably shopping with my friends. Please, help me :(
rachel7660
2010-04-19 15:17:34
@rachel7660: It's been a while since I've done Big-O proofs ;) Would you mind giving a clear definition of C and n0 in the question?
FrustratedWithFormsDesigner
2010-04-19 15:53:34
@rachel7660: C has to be a constant, so you can't choose C >= 2^n. If you can prove that C needs to be at least 2^n (i.e., not constant), then you have demonstrated a contradiction which means that statement 2 is false.
Daniel Stutzbach
2010-04-19 15:55:43
@Frustrated: For C and n0 see http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition (where C is called M and n0 is x0)
tanascius
2010-04-19 16:07:44
@FrustratedWithFormsDesigner: C is the constant. n0 is the minimal value of the function, so that it will perform worst case. Well, I am not good at memorizing terms.
rachel7660
2010-04-19 16:08:24