Big-O question - Algorithms

[sita]

Delete

 

[Dr.Peterson]

Use definition of Big-O to show that:

Please can someone give me a hint.

The problem is



to make it easier to find.

They gave you a hint; are you asking what it means? If they mean just to use the formula they state without proof, then all you really need to do is to apply the definition of Big O. What is that definition?

If you are asking how to prove the equation in the hint, you can do what they say and apply the formula for a geometric series.

Please let us know what parts you do understand, and state the definition you were given, so we can be sure of an appropriate starting point.

 

[sita]

The problem is

View attachment 10591

to make it easier to find.

They gave you a hint; are you asking what it means? If they mean just to use the formula they state without proof, then all you really need to do is to apply the definition of Big O. What is that definition?

If you are asking how to prove the equation in the hint, you can do what they say and apply the formula for a geometric series.

Please let us know what parts you do understand, and state the definition you were given, so we can be sure of an appropriate starting point.

Definition for Big-O

http://prntscr.com/lq3zuq

I just need a starting point for getting it done with the hint.

 

[Dr.Peterson]

Definition for Big-O

http://prntscr.com/lq3zuq

I just need a starting point for getting it done with the hint.

Please tell us what you don't understand about the hint! We need interaction in order to know what you need to be told.

A valuable way to show what you do or don't understand is to make an attempt (no matter how wrong you expect it to be) to follow the hint.

 

[sita]

figured

 

[Dr.Peterson]

Please see approaches taken:
1) http://prntscr.com/lq4jyx

2) http://prntscr.com/lq4kdo

3) http://prntscr.com/lq4kp5

Let me know which ones you suggest correct or not.

The first derives the formula they gave, which I don't think they require you to do, and very simply applies the definition of Big O. It looks fine, though I don't see why you would need to say 2n - 1 < 2n + 2n.

The second, I can't follow at all. Why does it say that 2n - 1 <= n? What is it trying to say?

The third doesn't deal with the main question, only with the geometric series.

All of them are lacking words. You really need to say what you are doing.

Where did these come from? Why are you asking about them?

 

[JeffM]

Please see approaches taken:
1) http://prntscr.com/lq4jyx

2) http://prntscr.com/lq4kdo

3) http://prntscr.com/lq4kp5

Let me know which ones you suggest correct or not.

The definition that you are using is

\(\displaystyle g(n) = O(f(n)) \iff \exists \ c \text { and } n_0 \text { such that } c > 0 < n_0 \text { and}\)

\(\displaystyle g(n) \le c * f(n) \text { for all } n \ge n_0.\)

That is perhaps not an ideal definition, but, under any common definition, you will need to determine what f(n) is? So, in your problem, what is f(n)?