Suppose that as a side hustle you run a website which offers image processing services. Each client uploads a single folder containing all of the pictures it wants you to process. Suppose your service receives uploads from K different clients and so has K folders which contain altogether N pictures, although without looking into each folder you don't know how the N pictures are distributed across the K folders. Your back-end dev team has developed two proprietary algorithms for processing images; we will call these algorithms A and B. They work as follows: • A takes a single folder as input and processes all images in this folder; it runs in time (1). .B takes a set of folders and immediately processes all images in all folders; it runs in time O(M) where M is the maximum number of pictures in any of the input folders. Assume furthermore that you have a helper function C which returns the folder with the maximum number of unprocessed photos; it runs in time 0. (Note: while it is unrealistic to assume that an algorithm runs in time 0, this is nevertheless a common practice in the study of algorithms. The idea is to encourage you to ignore the cost of executing C to let you focus on the bottleneck operations A and B.) Example. One idea is to simply invoke A on every one of the K folders, resulting in an O(K) time algorithm. Another idea is to simply run B to immediately process all images. This will work really well if each folder has O(1) pictures in it. However, both of these ideas work poorly if, for example, there is one folder which contains N/2 photos and N/2 other folders which each contain 1 photo each. In this case, both of these basic ideas would run in time (N). Design an algorithm which uses A, B and C and processes all photos in O(VN) time, regardless of how the N pictures are distributed in the K folders. Analyze your algorithm (i.e., prove that it processes all images and that the runtime is indeed O(√N)).
Suppose that as a side hustle you run a website which offers image processing services. Each client uploads a single folder containing all of the pictures it wants you to process. Suppose your service receives uploads from K different clients and so has K folders which contain altogether N pictures, although without looking into each folder you don't know how the N pictures are distributed across the K folders. Your back-end dev team has developed two proprietary algorithms for processing images; we will call these algorithms A and B. They work as follows: • A takes a single folder as input and processes all images in this folder; it runs in time (1). .B takes a set of folders and immediately processes all images in all folders; it runs in time O(M) where M is the maximum number of pictures in any of the input folders. Assume furthermore that you have a helper function C which returns the folder with the maximum number of unprocessed photos; it runs in time 0. (Note: while it is unrealistic to assume that an algorithm runs in time 0, this is nevertheless a common practice in the study of algorithms. The idea is to encourage you to ignore the cost of executing C to let you focus on the bottleneck operations A and B.) Example. One idea is to simply invoke A on every one of the K folders, resulting in an O(K) time algorithm. Another idea is to simply run B to immediately process all images. This will work really well if each folder has O(1) pictures in it. However, both of these ideas work poorly if, for example, there is one folder which contains N/2 photos and N/2 other folders which each contain 1 photo each. In this case, both of these basic ideas would run in time (N). Design an algorithm which uses A, B and C and processes all photos in O(VN) time, regardless of how the N pictures are distributed in the K folders. Analyze your algorithm (i.e., prove that it processes all images and that the runtime is indeed O(√N)).
Related questions
Question
Transcribed Image Text:Suppose that as a side hustle you run a website which offers image processing services. Each client uploads
a single folder containing all of the pictures it wants you to process. Suppose your service receives uploads
from K different clients and so has K folders which contain altogether N pictures, although without looking
into each folder you don't know how the N pictures are distributed across the K folders. Your back-end dev
team has developed two proprietary algorithms for processing images; we will call these algorithms A and
B. They work as follows:
• A takes a single folder as input and processes all images in this folder; it runs in time O(1).
• B takes a set of folders and immediately processes all images in all folders; it runs in time O(M) where
M is the maximum number of pictures in any of the input folders.
Assume furthermore that you have a helper function C which returns the folder with the maximum number
of unprocessed photos; it runs in time 0. (Note: while it is unrealistic to assume that an algorithm runs in
time 0, this is nevertheless a common practice in the study of algorithms. The idea is to encourage you to
ignore the cost of executing C to let you focus on the bottleneck operations A and B.)
Example. One idea is to simply invoke A on every one of the K folders, resulting in an O(K) time
algorithm. Another idea is to simply run B to immediately process all images. This will work really well if
each folder has O(1) pictures in it. However, both of these ideas work poorly if, for example, there is one
folder which contains N/2 photos and N/2 other folders which each contain 1 photo each. In this case, both
of these basic ideas would run in time O(N).
Design an algorithm which uses A, B and C and processes all photos in O(√N) time, regardless of how the
N pictures are distributed in the K folders. Analyze your algorithm (i.e., prove that it processes all images
and that the runtime is indeed O(√N)).
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 4 steps with 11 images
