1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
dimaraw [331]
3 years ago
6

The running time of Algorithm A is (1/4) n2+ 1300, and the running time of another Algorithm B for solving the same problem is 1

12n − 8. Assuming all other factors equal, at what input size(s) would we prefer one algorithm to the other?
Computers and Technology
1 answer:
Mnenie [13.5K]3 years ago
8 0

Answer:

Answer is explained below

Explanation:

The running time is measured in terms of complexity classes generally expressed in an upper bound notation called the big-Oh ( "O" ) notation. We need to find the upper bound to the running time of both the algorithms and then we may compare the worst case complexities, it is also important to note that the complexity analysis holds true (and valid) for large input sizes, so, for inputs with smaller sizes, an algorithm with higher complexity class may outperform the one with lower complexity class i.e, efficiency of an algorithm may vary in cases where input sizes are smaller & more efficient algorithm might be outperformed by the lesser efficient algorithms in those cases.

That's the reason why we consider inputs of larger sizes when comparing the complexity classes of the respective algorithms under consideration.

Now coming to our question for algorithm A, we have,

let F(n) = 1/4x² + 1300

So, we can tell the upper bound to the function O(F(x)) = g(x) = x2

Also for algorithm B, we have,

let F(x) = 112x - 8

So, we can tell the upper bound to the function O(F(x)) = g(x) = x

Clearly, algorithmic complexity of algorithm A > algorithmic complexity of algorithm B

Hence we can say that for sufficiently large inputs , algorithm B will be a better choice.

Now to find the exact location of the graph in which algorithmic complexity for algorithm B becomes lesser than

algorithm A.

We need to find the intersection point of the given two equations by solving them:

We have the 2 equations as follows:

y = F(x) = 1/4x² + 1300 __(1)

y = F(X) = 112x - 8 __(2)

Let's put the value of from (2) in (1)

=> 112x - 8 = 1/4x² + 1300

=> 112x - 0.25x² = 1308

=> 0.25x² - 112x + 1308 = 0

Solving, we have

=> x = (112 ± 106) / 0.5

=> x = 436, 12

We can obtain the value for y by putting x in any of the equation:

At x=12 , y= 1336

At x = 436 , y = 48824

So we have two intersections at point (12,1336) & (436, 48824)

So before first intersection, the

Function F(x) = 112x - 8 takes lower value before x=12

& F(x) = 1/4x² + 1300 takes lower value between (12, 436)

& F(x) = 112x - 8 again takes lower value after (436,∞)

Hence,

We should choose Algorithm B for input sizes lesser than 12

& Algorithm A for input sizes between (12,436)

& Algorithm B for input sizes greater than (436,∞)

You might be interested in
Clive wants to write a query that will display the names of the students who scored less than 10 in their final exams. Which num
Mice21 [21]
I'd go for <span>FLOOR(x)
</span>

The numerical function FLOOR(x) can be used to return the largest integer value that is less than or equal to the numerical expression provided. The numerical function CEILING (x) is the opposite of FLOOR(x) since it gives the smallest integer value that is greater or equal to the numerical expression.






6 0
3 years ago
Read 2 more answers
Banking Account
satela [25.4K]

Answer:

Here is the Python script solution.

Explanation:

#!/usr/bin/python

"""Types of bank accounts"""

# Assignment:

# Bank Account Manager - Create a class called Account which will be an abstract

# class for three other classes called CheckingAccount, SavingsAccount and

# BusinessAccount. Manage credits and debits from these accounts through an ATM

# style program.

from __future__ import print_function

def pct_to_dec(num):

"""Returns decimal version of percent"""

dec = float(num) / 100

return dec

class Account(object):

"""Creates an Account"""

def __init__(self, balance, int_rate, act_type, min_balance, **kwargs):

self.balance = balance

self.int_rate = int_rate

self.act_type = act_type

self.min_balance = min_balance

super(Account, self).__init__(**kwargs)

def __str__(self):

"""Returns formatted account type and balance"""

# Charge $25 fee if balance drops below minimum

if self.balance < self.min_balance:

self.balance -= 25

# Add interest

self.balance += round(self.balance * pct_to_dec(self.int_rate), 2)

return '{0}: ${1}'.format(self.act_type, self.balance)

class CheckingAccount(Account):

"""Creates a CheckingAccount Account"""

def __init__(self, **kwargs):

super(CheckingAccount, self).__init__(**kwargs)

class SavingsAccount(Account):

"""Creates a SavingsAccount Account"""

def __init__(self, **kwargs):

super(SavingsAccount, self).__init__(**kwargs)

class BusinessAccount(Account):

"""Creates a BusinessAccount Account"""

def __init__(self, **kwargs):

super(BusinessAccount, self).__init__(**kwargs)

# pylint: disable=C0103

ca1 = CheckingAccount(balance=500, int_rate=0.25, act_type='Checking Account',

min_balance=0)

sa1 = SavingsAccount(balance=50, int_rate=0.50, act_type='Savings Account',

min_balance=0)

ba1 = BusinessAccount(balance=4000, int_rate=0.75, act_type='Business Account',

min_balance=5000)

# Month #1 statement, initial deposits plus interest

print(ca1)

print(sa1)

print(ba1)

print('-------------')

# Month #2 statement plus interest

# Make deposit into checking

setattr(ca1, 'balance', (ca1.balance + 1000))

# Withdraw from checking

setattr(ca1, 'balance', (ca1.balance - 500))

# Make a deposit into savings

setattr(sa1, 'balance', (sa1.balance + 100))

print(ca1)

print(sa1)

print(ba1)

print('-------------')

# Month #3 statement plus interest

# Make deposit into checking

setattr(ca1, 'balance', (ca1.balance + 2500))

# Withdraw from checking

setattr(ca1, 'balance', (ca1.balance - 700))

# Make a deposit into savings

setattr(sa1, 'balance', (sa1.balance + 100))

# Make a deposit into business

setattr(ba1, 'balance', (ba1.balance + 1000))

print(ca1)

print(sa1)

print(ba1)

4 0
4 years ago
Which file extension takes less storage space?
anyanavicka [17]

I believe the answer would be the JPEG file extension.

4 0
3 years ago
Read 2 more answers
What is Digital Access, and why is it important for YOUR generation?
Harman [31]

“Our students were born with a mouse in their hands. The pervasive nature of digital culture has altered the way they think, and the way they learn. Education today is completely out of sync with this new reality.” an excerpt from Understanding the Digital Generation. The New ConnectionsThis eye-opening presentation provides a comprehensive look at how the pervasive nature of digital culture has and continues to change the brains of our students. As a result of these changes, they have developed learning styles and preferences which are in contrast to the traditional pedagogical approach. The New Connections provides a clear description of 10 core learning attributes of digital learners, and a pragmatic look at how we can teach effectively in an age when new technologies cascade onto the new digital landscape at an astonishing rate. Because of digital bombardment and the emergence of the new digital landscape, today’s youth process information, interact and communicate in fundamentally different ways than any previous generation before them. Meanwhile, many of us, having grown up in a relatively low-tech, stable, and predictable world, are constantly struggling with the speed of change, technological innovation, and the freedom to access the overwhelming sea of information online—all defining characteristics of the digital world of both today, and the swiftly-approaching future. Strategies That Work provides a comprehensive profile of several core learning attributes of digital learners, and the core teaching, learning, and assessment strategies that can be used to appeal to their digital lifestyle and learning preferences. You’ll gain a clear understanding of various research-based strategies to optimize learning for the digital generation in the new digital landscape.

7 0
3 years ago
Sincerely is an example of a salutation true or false
Setler79 [48]
No, I don't think so.
5 0
3 years ago
Read 2 more answers
Other questions:
  • Write a program to read as many test scores as the user wants from the keyboard (assuming at most 50 scores). Print the scores i
    13·1 answer
  • Where does the oracle11g server store information about objects in the database, including information about constraints?
    15·1 answer
  • What is the typical relationship between time and interest rate?
    12·1 answer
  • There are several methods of updating information and data on a webserver. We must consider who performs those updates upfront w
    9·2 answers
  • When a rectangular region is defined using an appropriate style, which value matches the specified edge of the clipping region t
    7·1 answer
  • What output is displayed when the code that follows is executed? HashMap sales = new HashMap&lt;&gt;(); sales.put("January", 389
    12·1 answer
  • Please help!!!! will mark brainliest!!
    7·2 answers
  • When you purchase donuts, they come in boxes of 12, so 24 donuts take 2 boxes. All donuts need to be in a box, so if you buy 13
    10·1 answer
  • Can you answer this question?
    9·1 answer
  • How to check the at&amp;t internet speed on my computer
    9·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!