reset password
Author Message
G190852562
Posts: 162
Posted 21:19 Dec 06, 2014 |

2. Can the answer also be no? Say I choose c = 1 and n_0 = 1.

4. Why is the answer a? 2^n = O(2^n-1) is incorrect as 2^n > 2^n-1. If n = 1, the inequality would be 2 > 1 which is false.

5. My question for this problem is similar to number 4.

And a general question: Whenever we see log(n) in Computer Science, we're always referring to log_2(n) and not log_10(n), right?

hal255
Posts: 51
Posted 21:33 Dec 06, 2014 |
AnonCS312 wrote:

2. Can the answer also be no? Say I choose c = 1 and n_0 = 1.

I believe this question asks which of the options can only be true. So, you just plug in the c values and see if the statement holds true. 

You can look at it the quick way, n <= c * n / 30.

So the n-value at the right is getting divided by 30, which means you need c to be 30 or higher. The only option is D, c is 200.

Last edited by hal255 at 21:34 Dec 06, 2014.
rabbott
Posts: 1649
Posted 21:34 Dec 06, 2014 |

Please ask about each question separately.

G190852562
Posts: 162
Posted 21:47 Dec 06, 2014 |
rabbott wrote:

Please ask about each question separately.

Wouldn't that flood the forum with too much threads?

I can't just simply divide my questions by quiz?

Last edited by G190852562 at 21:48 Dec 06, 2014.
hal255
Posts: 51
Posted 21:50 Dec 06, 2014 |
AnonCS312 wrote:

4. Why is the answer a? 2^n = O(2^n-1) is incorrect as 2^n > 2^n-1. If n = 1, the inequality would be 2 > 1 which is false.

This one got me a few times as well. But the general idea is to think BIG, as in n approaches some high number.

Now, you just factor out the 2^-1 from the 2^(n-1) which leaves you with ---> 2^(n) <= c * [ 2^n * 2^(-1) ]

Since 2^(-1) is a constant number, it can be combined with the constant c (call it c1 if you want) ---> 2^(n) <= c * [ 2^n * c1 ]

and becomes a new constant number (c2). --->  2^(n) <= c2 * [ 2^n]

Since c2 is just any old constant, let's just call it c again --->  2^(n) <= c * [ 2^n ]

Thus, statement still holds true.

G190852562
Posts: 162
Posted 21:50 Dec 06, 2014 |
hal255 wrote:
AnonCS312 wrote:

2. Can the answer also be no? Say I choose c = 1 and n_0 = 1.

I believe this question asks which of the options can only be true. So, you just plug in the c values and see if the statement holds true. 

You can look at it the quick way, n <= c * n / 30.

So the n-value at the right is getting divided by 30, which means you need c to be 30 or higher. The only option is D, c is 200.

Thanks.

What about number 4, 5, and my general question?

Edit: Posted before you had a chance to answer. Sorry about that. lol

Last edited by G190852562 at 21:51 Dec 06, 2014.
hal255
Posts: 51
Posted 21:53 Dec 06, 2014 |
AnonCS312 wrote:

5. My question for this problem is similar to number 4.

Errr... hmmm... Not sure why this answer results in the way it did. Now I'm starting to wonder if my answer for #4 was wrong.

Last edited by hal255 at 22:00 Dec 06, 2014.
G190852562
Posts: 162
Posted 21:59 Dec 06, 2014 |
hal255 wrote:
AnonCS312 wrote:

4. Why is the answer a? 2^n = O(2^n-1) is incorrect as 2^n > 2^n-1. If n = 1, the inequality would be 2 > 1 which is false.

This one got me a few times as well. But the general idea is to think BIG, as in n approaches some high number.

Now, you just factor out the 2^-1 from the 2^(n-1) which leaves you with ---> 2^(n) <= c * [ 2^n * 2^(-1) ]

Since 2^(-1) is a constant number, it can be combined with the constant c (call it c1 if you want) ---> 2^(n) <= c * [ 2^n * c1 ]

and becomes a new constant number (c2). --->  2^(n) <= c2 * [ 2^n]

Since c2 is just any old constant, let's just call it c again --->  2^(n) <= c * [ 2^n ]

Thus, statement still holds true.

Oh okay! That makes a lot of sense. lol That was definitely one tricky problem if you don't look at it carefully/think about ways to manipulate it.

ceejay562
Posts: 25
Posted 22:27 Dec 06, 2014 |

2^n = O(2^(n-1))   you can reduce this problem by dividing both sides by 2^(n-1) , which gives you   2^1 <= c*1  . so you can pick a constant c=1 which is true.  

2^n = O(2^n+1) divide both sides by 2^(n+1) leaves you with 1/n <= c*1. as n increases the the left side decreases. any constant >= 1 works. so it is true.

n^a = O(n^(a-1)) is false because dividing both sides by 2^(a-1)  leaves you with  n <= c*1. 

 

 

ceejay562
Posts: 25
Posted 22:32 Dec 06, 2014 |

sorry. for the first answer you can pick c=2 not c=1.

G190852562
Posts: 162
Posted 00:05 Dec 07, 2014 |
ceejay562 wrote:

sorry. for the first answer you can pick c=2 not c=1.

I understood, thanks. :)