My Math Forum Big-O question - Algorithms

 Computer Science Computer Science Forum

 December 2nd, 2018, 04:33 PM #1 Member   Joined: Oct 2017 From: Rumba Posts: 34 Thanks: 0 Big-O question - Algorithms Use definition of Big-O to show that: http://prntscr.com/lpv8mq Please can someone give me a hint.
 December 2nd, 2018, 08:06 PM #2 Senior Member   Joined: Sep 2016 From: USA Posts: 521 Thanks: 293 Math Focus: Dynamical systems, analytic function theory, numerics There is already a hint included in the exercise and it basically gives you the answer. What more do you want?
December 3rd, 2018, 05:59 AM   #3
Member

Joined: Oct 2017
From: Rumba

Posts: 34
Thanks: 0

Quote:
 Originally Posted by SDK There is already a hint included in the exercise and it basically gives you the answer. What more do you want?
A hint on how to use it

 December 3rd, 2018, 04:11 PM #4 Senior Member   Joined: May 2016 From: USA Posts: 1,210 Thanks: 497 I am going to use a slightly more general definition. $g(n) = O(f(n)) \text { as } n \rightarrow \infty \iff \exists \ c > 0 < n_0 \text { such that}$ $|f(n)| \le c * g(n) \text { for all } n \ge n_0.$ As I said at the other site, you first need to identify f(n). In this problem, $f(n) = 2n - 1 \text { for } n \ge 1.$ Can you think of a simple function that always exceeds |f(n)| if n is at least 1? Sure you can. $n \ge 1 \implies 2n > |2n - 1|.$ So what do you think are $c$ and $n_0$? Thanks from sita
December 3rd, 2018, 04:22 PM   #5
Member

Joined: Oct 2017
From: Rumba

Posts: 34
Thanks: 0

Quote:
 Originally Posted by JeffM1 I am going to use a slightly more general definition. $g(n) = O(f(n)) \text { as } n \rightarrow \infty \iff \exists \ c > 0 < n_0 \text { such that}$ $|f(n)| \le c * g(n) \text { for all } n \ge n_0.$ As I said at the other site, you first need to identify f(n). In this problem, $f(n) = 2n - 1 \text { for } n \ge 1.$ Can you think of a simple function that always exceeds |f(n)| if n is at least 1? Sure you can. $n \ge 1 \implies 2n > |2n - 1|.$ So what do you think are $c$ and $n_0$?
I got this:
http://prntscr.com/lqc7a7

December 3rd, 2018, 04:30 PM   #6
Senior Member

Joined: May 2016
From: USA

Posts: 1,210
Thanks: 497

Quote:
 Originally Posted by sita I got this: http://prntscr.com/lqc7a7
Is $|2n - 1| \le 2 * n \text { for all } n \ge 1|$?

If so, c = 2, g(n) = n, and n_0 = 1 satisfies the definition.

You seem to be making something fairly simple really difficult.

STUDY the definition until you understand it.

Last edited by JeffM1; December 3rd, 2018 at 05:12 PM.

December 3rd, 2018, 05:19 PM   #7
Member

Joined: Oct 2017
From: Rumba

Posts: 34
Thanks: 0

Quote:
 Originally Posted by JeffM1 Is $|2n - 1| \le 2 * n \text { for all } n \ge 1|$? If so, c = 2, g(n) = n, and n_0 = 1 satisfies the definition. You seem to be making something fairly simple really difficult. STUDY the definition until you understand it.

 Tags algorithms, bigo, question

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post sita Computer Science 3 November 3rd, 2018 10:36 AM sita Computer Science 6 November 2nd, 2018 07:57 PM OriaG Calculus 9 June 8th, 2015 09:13 PM iKnowAll Computer Science 1 February 7th, 2014 01:16 PM vamsi Number Theory 0 February 25th, 2013 10:35 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top