My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
November 2nd, 2018, 10:00 AM   #1
Newbie
 
Joined: Oct 2017
From: Rumba

Posts: 29
Thanks: 0

Algorithms question

https://prnt.sc/ldn10r
Suppose there are two algorithms that solve the same problem:
$\ \ \ \ \ $ - $\ $ one algorithm performs $4n^2 + n + 300$ basic operations;
$\ \ \ \ \ $ - $\ $ another algorithm performs $101n - 100$ basic operations,
where $n$ is the input size, $n \ge 1$.
(a) Which one would you prefer, assuming all other factors are equal? Hint: your choice may depend on the value of $n$.
(b) Explain how the two algorithms can be combined so that the resulting algorithm works fast for all input sizes?

How would I answer part (b)?

Last edited by skipjack; November 2nd, 2018 at 10:33 AM.
sita is offline  
 
November 2nd, 2018, 10:50 AM   #2
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,192
Thanks: 489

Quote:
Originally Posted by sita View Post
https://prnt.sc/ldn10r
Suppose there are two algorithms that solve the same problem:
$\ \ \ \ \ $ - $\ $ one algorithm performs $4n^2 + n + 300$ basic operations;
$\ \ \ \ \ $ - $\ $ another algorithm performs $101n - 100$ basic operations,
where $n$ is the input size, $n \ge 1$.
(a) Which one would you prefer, assuming all other factors are equal? Hint: your choice may depend on the value of $n$.
(b) Explain how the two algorithms can be combined so that the resulting algorithm works fast for all input sizes?

How would I answer part (b)?
What did you get as an answer to (a)?

Do you see how that piece of information may help you to solve (b)?
JeffM1 is offline  
November 2nd, 2018, 10:58 AM   #3
Newbie
 
Joined: Oct 2017
From: Rumba

Posts: 29
Thanks: 0

Quote:
Originally Posted by JeffM1 View Post
What did you get as an answer to (a)?

Do you see how that piece of information may help you to solve (b)?
A) (Blue) first algorithm will take: 4n² + n + 300 = O(n2) time from 100 to 121

Whereas (Red) second algorithm 101n - 100 = O(n) time. Hence second algorithm is faster. In 0 to 100 and from 121 and beyond.

So in order to get faster results in all kinds of input, we can combine these algorithms.

T(n) = T1(n) or T2(n) , where T1(n) if n = 100 to 121 and T2(n) if n = 0 to 100 or if n > 121

Where T1(n) = 4n² + n + 100 and T2(n) = 101n - 100.


I'm not sure how to write as pseudocode with if else statements with inequality for (b) for e.g.

if n < _

use algo 1

else

use algo 2

Last edited by skipjack; November 2nd, 2018 at 07:29 PM.
sita is offline  
November 2nd, 2018, 11:56 AM   #4
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,192
Thanks: 489

Quote:
Originally Posted by sita View Post
A) (Blue) first algorithm will take: 4n² + n + 300 = O(n2) time from 100 to 121

Whereas (Red) second algorithm 101n - 100 = O(n) time. Hence second algorithm is faster. In 0 to 100 and from 121 and beyond.

So in order to get faster results in all kinds of input, we can combine these algorithms.

T(n) = T1(n) or T2(n) , where T1(n) if n = 100 to 121 and T2(n) if n = 0 to 100 or if n > 121

Where T1(n) = 4n² + n + 100 and T2(n) = 101n - 100.


I'm not sure how to write as pseudocode with if else statements with inequality for (b) for e.g.

if n < _

use algo 1

else

use algo 2
$\displaystyle 4n^2 + n + 300 = 101n - 100 \implies 4n^2 - 100n + 400 \implies n = \frac{100 \pm \sqrt{10000 - 4(4)(400)}}{2 * 4} =$

$\displaystyle \frac{100 \pm \sqrt{3600}}{8} = \frac{100 \pm 60}{8} = 5 \text { or } 20.$

Say n = 3.

$4(3)^2 + 3 + 300 = 339. \text { BUT } 101(3) - 100 = 203.$

So if n < 6, the red algorithm is as fast or faster than the blue algorithm because addend 300 is the dominant term.

Say n = 10.

$4(10)^2 + 10 + 300 = 710. \text { BUT } 101(10) - 100 = 910.$

So if 5 < n < 21, the blue algorithm is as fast or faster than the red algorithm because the 101n is the dominant term.

Say n = 21.

$4(21)^2 + 21 + 300 = 2085. \text { BUT } 101(21) - 100 = 2021.$

So if 19 < n, the red algorithm is as fast or faster than the blue algorithm because the 4n^2 is the dominant term.


If n < 6, go to red.

If n > 20, go to red.

blue code. Go to print.

red code.

print.

Last edited by skipjack; November 2nd, 2018 at 07:35 PM.
JeffM1 is offline  
November 2nd, 2018, 11:58 AM   #5
Member
 
Joined: Jan 2016
From: Athens, OH

Posts: 91
Thanks: 47

Actually, this illustrates a problem with completely relying on the order of an algorithm. For your given problem you want to know for what n is
$$101n-100\leq 4n^2+n+300$$
Simple algebra shows that the above inequality is true precisely for
$$1\leq n\leq5\text{ or } 20\leq n$$
johng40 is offline  
November 2nd, 2018, 12:38 PM   #6
Newbie
 
Joined: Oct 2017
From: Rumba

Posts: 29
Thanks: 0

Quote:
Originally Posted by JeffM1 View Post
$\displaystyle 4n^2 + n + 300 = 101n - 100 \implies 4n^2 - 100n + 400 \implies n = \frac{100 \pm \sqrt{10000 - 4(4)(400)}}{2 * 4} =$

$\displaystyle \frac{100 \pm \sqrt{3600}}{8} = \frac{100 \pm 60}{8} = 5 \text { or } 20.$

Say n = 3.

$4(3)^2 + 3 + 300 = 339. \text { BUT } 101(3) - 100 = 203.$

So if n < 6, the red algorithm is as fast or faster than the blue algorithm because addend 300 is the dominant term.

Say n = 10.

$4(10)^2 + 10 + 300 = 710. \text { BUT } 101(10) - 100 = 910.$

So if 5 < n < 21, the blue algorithm is as fast or faster than the red algorithm because the 101n is the dominant term.

Say n = 21.

$4(21)^2 + 21 + 300 = 2085. \text { BUT } 101(21) - 100 = 2021.$

So if 19 < n, the red algorithm is as fast or faster than the blue algorithm because the 4n^2 is the dominant term.


If n < 6, go to red.

If n > 20, go to red.

blue code. Go to print.

red code.

print.
Thank you, this has helped me picture it better.

Appreciate it

Last edited by skipjack; November 2nd, 2018 at 07:36 PM.
sita is offline  
November 2nd, 2018, 07:57 PM   #7
Global Moderator
 
Joined: Dec 2006

Posts: 19,878
Thanks: 1834

4n² + n + 300 - (101n - 100) = 4(n - 5)(n - 20), which exceeds 0 only for n < 5 or n > 20.
skipjack is offline  
Reply

  My Math Forum > Science Forums > Computer Science

Tags
algorithms, question



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Difficult question on efficiency and algorithms OriaG Calculus 9 June 8th, 2015 09:13 PM
hello all :) I don't know where I can put algorithms and please don't block this )) Schoff43 Algebra 2 November 22nd, 2014 12:45 AM
Algorithms (any help?) iKnowAll Computer Science 1 February 7th, 2014 01:16 PM
Analysis of algorithms, please help OriaG Applied Math 1 August 28th, 2013 04:41 AM
Mod Algorithms. vamsi Number Theory 0 February 25th, 2013 10:35 PM





Copyright © 2018 My Math Forum. All rights reserved.