User Name Remember Me? Password

 Computer Science Computer Science Forum

 December 2nd, 2018, 03:33 PM #1 Member   Joined: Oct 2017 From: Rumba Posts: 39 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, 07:06 PM #2 Senior Member   Joined: Sep 2016 From: USA Posts: 635 Thanks: 401 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, 04:59 AM   #3
Member

Joined: Oct 2017
From: Rumba

Posts: 39
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, 03:11 PM #4 Senior Member   Joined: May 2016 From: USA Posts: 1,310 Thanks: 551 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, 03:22 PM   #5
Member

Joined: Oct 2017
From: Rumba

Posts: 39
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, 03:30 PM   #6
Senior Member

Joined: May 2016
From: USA

Posts: 1,310
Thanks: 551

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 04:12 PM. December 3rd, 2018, 04:19 PM   #7
Member

Joined: Oct 2017
From: Rumba

Posts: 39
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.
Thanks i understand it now, please respond to your private message. Tags algorithms, bigo, question Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded Mode Similar Threads Thread Thread Starter Forum Replies Last Post sita Computer Science 3 November 3rd, 2018 09:36 AM sita Computer Science 6 November 2nd, 2018 06:57 PM OriaG Calculus 9 June 8th, 2015 08:13 PM iKnowAll Computer Science 1 February 7th, 2014 12:16 PM vamsi Number Theory 0 February 25th, 2013 09:35 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top

Copyright © 2019 My Math Forum. All rights reserved.      