How to prove this statement of big o notation?

10,784

Solution 1

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

Solution 2

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.

Share:
10,784
rachel7660
Author by

rachel7660

Updated on June 05, 2022

Comments

  • rachel7660
    rachel7660 over 1 year

    How to prove this:

    1. 4n = O(8n)
    2. 8n = O(4n)?

    So what are the C and n0 values for both cases?

    • rachel7660
      rachel7660 over 13 years
      I am terribly sorry, I mis-type the question. Can you guys re-answer the question (edited section)? Or should I post as a new question? I am really sorry :(
    • paxdiablo
      paxdiablo over 13 years
      @rachel, I've tidied it up as best I could but I'm still not sure I understand the question. Leave a comment on how you want it changed and we'll do our best to fix it. Example: did you mean "O(4^n) = O(8^n)"?
    • rachel7660
      rachel7660 over 13 years
      @paxdiable: Thanks for fixing. But will it cause any confusion as the answers dont match the question? Unless, the sharptooth and JC edit their answer. (I hope they will)
    • paxdiablo
      paxdiablo over 13 years
      S**t happens :-) It wouldn't be the first time the final question changes and hopefully (1) sharptooth and JC will be watching and (2) people will take it easy on them if they're not watching (since it's evident the question has changed). We'll leave a notification. Unfortunately, the question may still not make sense. Is it currently correct or do you want more changes?
    • rachel7660
      rachel7660 over 13 years
      @paxdiablo: You are so nice :)
    • sharptooth
      sharptooth over 13 years
      Wow! With the edits I seriously doubt that the second statement holds true.
    • rachel7660
      rachel7660 over 13 years
      Omg... @sharptooth: what makes you think so? Please... I have been struggling this questions for 2 days. Come on, help me!!!!!!!
    • kriss
      kriss over 13 years
      @rachel: there should be some indication about n : most likely (n -> infinity) that's the most usual case but without that the question is incomplete.
    • rachel7660
      rachel7660 over 13 years
      @kriss: Thats the complete question. I am analyzing tanascius answer. I think, I am there. He is really a nice + patient guru
    • kriss
      kriss over 13 years
      @rachel: ok, then it's definitely n going to infinity, sometimes it's considered as "implicit". I suggest you replace your initial equations with inequations (as described in wikipedia) and notice you just have positive numbers. All is left is very simple math without any confusing big-O left. But I guess you are nearing that point with the help of tanascius.
    • rachel7660
      rachel7660 over 13 years
      @kriss: I am going to sleep soon. very tired, can you help me on another questions? You can see the links under tanascius answer's comments. its 4 am here ..@_@
  • rachel7660
    rachel7660 over 13 years
    @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
    rachel7660 over 13 years
    (1)4^n <= C * 2^n * 4^n Thus, 2 is the C (2) 2^n <= C
  • rachel7660
    rachel7660 over 13 years
    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?
  • tanascius
    tanascius over 13 years
    @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.
  • rachel7660
    rachel7660 over 13 years
    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
    rachel7660 over 13 years
    So, for case 2, its an invalid statement? How about case 1? C is 2, n0 = 0??
  • tanascius
    tanascius over 13 years
    @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
    tanascius over 13 years
    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 ...
  • FrustratedWithFormsDesigner
    FrustratedWithFormsDesigner over 13 years
    @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?
  • Daniel Stutzbach
    Daniel Stutzbach over 13 years
    @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.
  • tanascius
    tanascius over 13 years
    @Frustrated: For C and n0 see en.wikipedia.org/wiki/Big_O_notation#Formal_definition (where C is called M and n0 is x0)
  • rachel7660
    rachel7660 over 13 years
    @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
    rachel7660 over 13 years
    @tanascius: Thanks. You are really a big help.
  • tanascius
    tanascius over 13 years
    @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 ...
  • rachel7660
    rachel7660 over 13 years
    @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.
  • tanascius
    tanascius over 13 years
    @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
  • rachel7660
    rachel7660 over 13 years
    @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?
  • tanascius
    tanascius over 13 years
    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
    tanascius over 13 years
    @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.
  • rachel7660
    rachel7660 over 13 years
    @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?
  • tanascius
    tanascius over 13 years
    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 ...
  • kriss
    kriss over 13 years
    @rachel: for case 2. Can a function going downward get higher than any fixed value greater than the initial one.
  • rachel7660
    rachel7660 over 13 years
    @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........
  • tanascius
    tanascius over 13 years
    @rachel ... no problem, I am happy as long as this all lead to anything :)
  • rachel7660
    rachel7660 over 13 years
    @tan: I Love u ^_^. Oh ya, now I understand why you say case2 is invalid statement. I am so happy now :) :) :)
  • tanascius
    tanascius over 13 years
    @rachel: great ... that was my longest comment-based conversation on SO so far :) bye ^^
  • rachel7660
    rachel7660 over 13 years
    @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
  • tanascius
    tanascius over 13 years
    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
  • rachel7660
    rachel7660 over 13 years
    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
    rachel7660 over 13 years