My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Thanks Tree2Thanks
  • 1 Post By JeffM1
  • 1 Post By JeffM1
Reply
 
LinkBack Thread Tools Display Modes
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.
sita is offline  
 
December 2nd, 2018, 08:06 PM   #2
SDK
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?
SDK is offline  
December 3rd, 2018, 05:59 AM   #3
Member
 
Joined: Oct 2017
From: Rumba

Posts: 34
Thanks: 0

Quote:
Originally Posted by SDK View Post
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
sita is offline  
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
JeffM1 is offline  
December 3rd, 2018, 04:22 PM   #5
Member
 
Joined: Oct 2017
From: Rumba

Posts: 34
Thanks: 0

Quote:
Originally Posted by JeffM1 View Post
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
sita is offline  
December 3rd, 2018, 04:30 PM   #6
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,210
Thanks: 497

Quote:
Originally Posted by sita View Post
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 from sita

Last edited by JeffM1; December 3rd, 2018 at 05:12 PM.
JeffM1 is offline  
December 3rd, 2018, 05:19 PM   #7
Member
 
Joined: Oct 2017
From: Rumba

Posts: 34
Thanks: 0

Quote:
Originally Posted by JeffM1 View Post
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.
sita is offline  
Reply

  My Math Forum > Science Forums > Computer Science

Tags
algorithms, bigo, question



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Algorithms question help sita Computer Science 3 November 3rd, 2018 10:36 AM
Algorithms question sita Computer Science 6 November 2nd, 2018 07:57 PM
Difficult question on efficiency and algorithms OriaG Calculus 9 June 8th, 2015 09:13 PM
Algorithms (any help?) iKnowAll Computer Science 1 February 7th, 2014 01:16 PM
Mod Algorithms. vamsi Number Theory 0 February 25th, 2013 10:35 PM





Copyright © 2018 My Math Forum. All rights reserved.