Description: ------------ Derive in details the complexity of the following code
ID: 3869810 • Letter: D
Question
Description: ------------ Derive in details the complexity of the following code fragments in terms of the Big-O notation: 1) for i = 1 to n do for j = 1 to n do x = 2 * y z = x-- 2) for i = 1 to n do j = n while j != 1 do x++ j = j / 2 3) i = 1 while i != n do i++ 4) for i = 1 to n do if i == 1 or i == n or i == 3 do for j = 1 to n do x++ Provide the corresponding big-O notation for the following functions: n^2 + 3n - 7 5n^3 - 3n^2 + 8n - 2 lg(n) - 2 + 3n nlg(n) - n + 3 Part 2 (70% of the grade) PROBLEM DESCRIPTION: ^^^^^^^^^^^^^^^^^^^^ Nobody wants a nuclear power plant in their neighborhood. Unfortunately, the governor must locate a nuclear power plant somewhere inside a 25 square mile area containing four cities. The governor, being primarily concerned with reelection, desires to locate the plant in the location which will cause the least amount of unhappiness among the constituents. In this lab, you will write a program to assist the governor in this difficult decision. METHOD: ^^^^^^^ Assume each city is located in an integer-pair (x, y) valued location within a 25 x 25 square mile area. For example, a city can be located at (4, 19), but not at (4.5, 19.8). In other words, there are no real valued coordinate for a location of a city. Your program will consider each integer-pair valued location within the area as a possible site for the nuclear plant, starting at (1, 1) and continuing across each row until the final site (25, 25) is reached. At each possible location for the nuclear plant, your program will compute the average unhappiness if the plant were located there. The following two rules will be used to compute the unhappiness for a city. 1) If the plant is within two miles or less of a city, the unhappiness is infinite (that is, assign a very large number to the unhappiness for that city). 2) Otherwise, the unhappiness is equal to the population of the city divided by the distance of the plant from the city. The average unhappiness equals: Avg. Unhappiness = Sum of the unhappiness of 4 cities / The total state's population. Your program should select the site at which the average unhappiness is smallest. INPUT: ^^^^^^ The user should be prompted to enter the x and y coordinates and the population for each of the four cities from the keyboard. Each coordinate should be checked to ensure it is between 1 and 25. If not, the user should be prompted to enter a value which is in the correct range. The population should be entered in thousands of people. For example, if the population is 10,000, the user should input 10. OUTPUT: ^^^^^^^ The program should print a message indication the coordinates where the plant should be located. Following that message, the user should be prompted to enter a 1 to view a map of the scenario or a 0 to exit the program. An Example Scenario: Enter the x and y for City 1 : 1 1 Enter the Population for City 1: 10 Enter the x and y for City 2 : 1 25 Enter the Population for City 2: 10 Enter the x and y for City 3 : 25 1 Enter the Population for City 3: 10 Enter the x and y for City 4 : 25 25 Enter the Population for City 4: 10 ********** Locate the Plant At: 13 13 Enter 1 to view a Map of the scenario, or 0 to exit: 1 MAP OF SCENARIO --------------- C2<><><><><><><><><><><><><><><><><><><><><><><>C4 <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><>PP<><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> <><><><><><><><><><><><><><><><><><><><><><><><><> C1<><><><><><><><><><><><><><><><><><><><><><><>C3 Note: The previous scenario is just an example, you need to create your own test cases to make sure that your program produces the correct results. Required Implementation: ^^^^^^^^^^^^^^^^^^^^^^^ Implement a State.java file that contains the State class. The state class contains all the getters and setters for the data. It also contains the methods that reads in the input calculates the location of the plant, and displays the output. Another file is required is StatePlant.java which contains your main program and all it does is instantiate the state, read the input for the state, calculate the location, print the location, and based on the user's input, print the map. So the main should be simple and just contains: State s = new State(); // you can have your own constructor if you'd like s.read_input(); // this should populate the values. or you can read // them in main an pass them here, it's up to you. s.calc_plant(); // print the location of the plant after you calculate // ask the user if he/she wants to display the map if so s.display_map();
Explanation / Answer
Solution:
1)
The code has two nested loops which are running n number of times each linearly which means both of them will run n number of times.
so the loops will execute like this
1 2 3 ...............................................n
1 to n 1 to n 1 to n .......................................1 to n
total number of times the statement with the loop will be executed is n*n= n^2
Time complexity T(n)= O(n^2)
2)
This one also has two nested loops but this time the inner loop (while loop) is controlled by the value of j which is changing to j/2 at each iteration this means that this loop will run
if the value of n is 1024
then
1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, terminate
this means that this loop is behaving like log n
and the outer loop is running n number of times so the time complexity is
T(n)= O(n log n)
3)
This code is running simply n number of times until the value of i becomes n so the time complexity
T(n)= O(n)
4)
Here, the inner loop will be running linearly only of value of i is 1, n, or 3 and since outer loop is running n number of times linearly this means that 3 times the inner loop will get the chance of running so the total number of executions will be 3n, and time complexity
T(n)= O(n).
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)