We've seen that asymptotic notations – 0-, N-, and O-notation – are a tool for focusing on the general shape of a function as opposed to its finer-grained details. We've seen some details that are clearly too fine-grained to be considered, such as constant factors and lower-order terms (e.g., 8n in the function n? + 8n), while others are fundamental and shouldn't be ignored. One thing we've not yet considered, but that will show up in many places in this course, is the effect of having multiple variables in a function. While we quite often use the variable n when the variable represents the size of a problem, not all problems' sizes can be described with one variable, which leaves us with the interesting question of what happens to additional variables in asymptotic notations. Let's consider that problem by thinking about a few subtly different scenarios. 1. Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Suppose, too, that we know for sure that m is always [n/2] (i.e., the floor of one-half of n). What is an asymptotic notation that best describes the time required to set all of the integers to zero? 2. Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Assume that both n and m are positive integers, but there is otherwise no limitation on how they relate to one another. What is an asymptotic notation that best describes the time required to set all of the integers to zero? 3. Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Assume that both n and m are positive integers, but there is otherwise no limitation on how they relate to one another. What is an asymptotic notation that best describes the time required to set only some of the integers – namely, all of the integers in the first sub-vector, then only the first integer in all the other sub-vectors – to zero? In each case, make sure to briefly explain your reasoning. None of them requires more than a couple of sentences, but simply stating an asymptotic notation is not enough here; you need to tell us why.
We've seen that asymptotic notations – 0-, N-, and O-notation – are a tool for focusing on the general shape of a function as opposed to its finer-grained details. We've seen some details that are clearly too fine-grained to be considered, such as constant factors and lower-order terms (e.g., 8n in the function n? + 8n), while others are fundamental and shouldn't be ignored. One thing we've not yet considered, but that will show up in many places in this course, is the effect of having multiple variables in a function. While we quite often use the variable n when the variable represents the size of a problem, not all problems' sizes can be described with one variable, which leaves us with the interesting question of what happens to additional variables in asymptotic notations. Let's consider that problem by thinking about a few subtly different scenarios. 1. Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Suppose, too, that we know for sure that m is always [n/2] (i.e., the floor of one-half of n). What is an asymptotic notation that best describes the time required to set all of the integers to zero? 2. Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Assume that both n and m are positive integers, but there is otherwise no limitation on how they relate to one another. What is an asymptotic notation that best describes the time required to set all of the integers to zero? 3. Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Assume that both n and m are positive integers, but there is otherwise no limitation on how they relate to one another. What is an asymptotic notation that best describes the time required to set only some of the integers – namely, all of the integers in the first sub-vector, then only the first integer in all the other sub-vectors – to zero? In each case, make sure to briefly explain your reasoning. None of them requires more than a couple of sentences, but simply stating an asymptotic notation is not enough here; you need to tell us why.
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
100%
![We've seen that asymptotic notations
O-, Q-, and O-notation
are a tool for focusing on the general shape of a function as opposed to its finer-grained details. We've seen some details that are clearly
too fine-grained to be considered, such as constant factors and lower-order terms (e.g., 8n in the function n2 + 8n), while others are fundamental and shouldn't be ignored.
One thing we've not yet considered, but that will show up in many places in this course, is the effect of having multiple variables in a function. While we quite often use the variable n when the variable
represents the size of a problem, not all problems' sizes can be described with one variable, which leaves us with the interesting question of what happens to additional variables in asymptotic notations.
Let's consider that problem by thinking about a few subtly different scenarios.
1. Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Suppose, too, that we know for sure that m is always [n/2] (i.e., the floor of one-half of n). What
is an asymptotic notation that best describes the time required to set all of the integers to zero?
2. Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Assume that both n and m are positive integers, but there is otherwise no limitation on how they
relate to one another. What is an asymptotic notation that best describes the time required to set all of the integers to zero?
3. Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Assume that both n and m are positive integers, but there is otherwise no limitation on how they
relate to one another. What is an asymptotic notation that best describes the time required to set only some of the integers - namely, all of the integers in the first sub-vector, then only the first integer
in all the other sub-vectors
- to zero?
In each case, make sure to briefly explain your reasoning. None of them requires more than a couple of sentences, but simply stating an asymptotic notation is not enough here; you need to tell us why.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fe5f558a7-14fc-4024-84d6-4debb1adc6f6%2F783e4f81-34d5-4dad-8f82-76204e3c6005%2Funzwozj_processed.png&w=3840&q=75)
Transcribed Image Text:We've seen that asymptotic notations
O-, Q-, and O-notation
are a tool for focusing on the general shape of a function as opposed to its finer-grained details. We've seen some details that are clearly
too fine-grained to be considered, such as constant factors and lower-order terms (e.g., 8n in the function n2 + 8n), while others are fundamental and shouldn't be ignored.
One thing we've not yet considered, but that will show up in many places in this course, is the effect of having multiple variables in a function. While we quite often use the variable n when the variable
represents the size of a problem, not all problems' sizes can be described with one variable, which leaves us with the interesting question of what happens to additional variables in asymptotic notations.
Let's consider that problem by thinking about a few subtly different scenarios.
1. Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Suppose, too, that we know for sure that m is always [n/2] (i.e., the floor of one-half of n). What
is an asymptotic notation that best describes the time required to set all of the integers to zero?
2. Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Assume that both n and m are positive integers, but there is otherwise no limitation on how they
relate to one another. What is an asymptotic notation that best describes the time required to set all of the integers to zero?
3. Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Assume that both n and m are positive integers, but there is otherwise no limitation on how they
relate to one another. What is an asymptotic notation that best describes the time required to set only some of the integers - namely, all of the integers in the first sub-vector, then only the first integer
in all the other sub-vectors
- to zero?
In each case, make sure to briefly explain your reasoning. None of them requires more than a couple of sentences, but simply stating an asymptotic notation is not enough here; you need to tell us why.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 3 steps
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY