-4

I want to learn how to approach the following question:

Which of the following function is larger by order of growth?

(1/3)^n or 17?

I have tried to find the answer, but I was unable to find a clear and straight forward explanation for how to calculate this.

  • 2
    Any analysis of algorithms book will cover this. Alternatively, see [here](https://mitpress.mit.edu/sicp/full-text/sicp/book/node17.html). – Ami Tavory Mar 09 '16 at 18:01
  • 1
    Possible duplicate of [Plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) – Kevin Mar 09 '16 at 18:04
  • @KevinWells, to be fair, he's asking how to find/calculate order, not what it is. I would say that this is a better candidate for duplicity: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it . Though the question does seem to imply that he doesn't understand it, either. – goodguy5 Mar 09 '16 at 18:08
  • 1
    @goodguy5 I disagree. The issue he is having seems to stem from a basic lack of understanding of what algorithmic complexity is. The question you linked has to do with calculating what the complexity is for a given algorithm, but he already has the big O complexity given to him, he just needs to compare two kinds of complexity and say which one is larger. Therefore the question I linked should help him because it goes over what the different kinds of complexity are and what they mean – Kevin Mar 09 '16 at 18:11
  • I have problem when n goes on exponent. –  Mar 09 '16 at 18:13
  • @KevinWells, It seems that you are correct. I was going originally off of what he said, rather than the context it was in. The first two comments seem to most thoroughly address this issue. – goodguy5 Mar 09 '16 at 18:14
  • I have a lot of slides about BIG O notation but I want the answer of this specific question –  Mar 09 '16 at 18:16
  • @Iony What do you mean when n goes on exponent? Are you saying you are having trouble with exponential growth? Is it something that isn't covered in the answer I linked you to? The top answer on the other question definitely covers exponential growth – Kevin Mar 09 '16 at 18:17
  • @Kevin Wells.. Kindly refer me some other link. There is no any answer which defines my problem. They are just talking about linear and quadratic generally. –  Mar 09 '16 at 18:25
  • @Iony Yes, they are talking about the general idea of what big O complexity is, and if you read through it and understand what they are saying, it will give you the answer to your question – Kevin Mar 09 '16 at 18:35

1 Answers1

2

This problem is unlike most examples because neither function grows in the sense of "increasing as n increases".

First, f(n) = 17 is a constant. No matter what n is, f(n) is 17.

Now, g(n) = (1/3)^n actually decreases as n increases (1/3, 1/9, 1/27, ..., with the limit being zero as n goes to infinity). So from the definition of big O, it's easy to find a constants c and n0 such that

c*(1/3)^(n) <= 17,   n >= n0

One choice is just c = n0 = 1, so g = O(f).

chepner
  • 497,756
  • 71
  • 530
  • 681
  • Sorry i wrote it mistakely –  Mar 09 '16 at 18:33
  • That was my mistake, during my edit of the question I somehow accidentally changed `(1/3)n` to `(1/3)^n`, which is obviously very different – Kevin Mar 09 '16 at 18:33
  • @KevinWells Ah, well, then it's easy. (1/3)n grows, 17 doesn't. They are both O(n), but while 17 = O(1) as well but 1/3n is not. – chepner Mar 09 '16 at 18:36
  • Actually I have slides of my teacher.. Your answer matches when `(1/3)^n=O(17)`. But if we check it for `17=O(1/3)^n` then it returns value of c like this `c>17*3^n` –  Mar 09 '16 at 18:39
  • @Iony You can't prove that 17 = O(1/3^n), because it's false. `c` and `n0` have to be constants. No matter what constant `c > 0` you pick, eventually `1/3^n` will be smaller than `17c`. – chepner Mar 09 '16 at 18:41
  • 1
    @Iony It seems clear that you don't understand what big O complexity is, you need to figure that out before you can ask a coherent question here, or ask a more specific question about what you don't understand – Kevin Mar 09 '16 at 18:43
  • @Kevin Wells.. I know about Big O notation but i was little bit confused about this questions because I have sense of weird explanation for this question –  Mar 09 '16 at 18:47
  • 2
    So is the function in the original question supposed to be `(1/3)^n`? The edit history is very confusing at this point. – chepner Mar 09 '16 at 18:47