You are running algorithm with squared complexity on data with 100 elements and it takes 10...

Question

Question

You are running algorithm with squared complexity on data with 100 elements and it takes 10 seconds. How much time do you expect the algorithm will take when executed on data with 1000 elements?
Order the following: O(n²), O(12 + 7n), O(n log(n) + 300 n² + 1/125 n³)

Answer 1

Answer #1

Solutions:
1) Given that the algorithm has squared complexity. This means that it takes (n2) time. Let the algorithm take cn2

time where n is the size of the input to the algorithm.Given n=100 and the time taken is 10s.

=> c (1002) = 10

=> c= 10/ 10000

=> c= 10-3

Now for n=1000 elements, the time taken is:

T= c (n2)

= 10-3 x 10002

= 1000 s

Hence tiume taken is 1000 seconds.

2) The decreasing order of the time complexities is:

O(n log(n) + 300 n2 + 1/125 n3) > O(n2) > O(12 + 7n)

The lower order terms can be omitted and the terms reduce to O(n3) , O(n2) and O(n) respectively.

Answer 2

Similar Homework Help Questions

Suppose that an algorithm takes 30 seconds for an input of 224 elements (with some particular,...

Suppose that an algorithm takes 30 seconds for an input of 224 elements (with some particular, but unspecified speed in instructions per second). Estimate how long the same algorithm, running on the same hardware, would take if the input contained 230 elements, and that the algorithm's complexity function is: Big theta not Big O a) Big theta(N) b) Big theta (log N) c) Big theta (N log N) d) Big theta(N^2) Assume that the low-order terms of the complexity functions...
7. What is the worst-case running time complexity of an algorithm with the recurrence relation T(N)...

7. What is the worst-case running time complexity of an algorithm with the recurrence relation T(N) = 2T(N/4) + O(N2)? Hint: Use the Master Theorem.
1. (10 points) Write an efficient iterative (i.e., loop-based) function Fibonnaci(n) that returns the nth Fibonnaci...

1. (10 points) Write an efficient iterative (i.e., loop-based) function Fibonnaci(n) that returns the nth Fibonnaci number. By definition Fibonnaci(0) is 1, Fibonnaci(1) is 1, Fibonnaci(2) is 2, Fibonnaci(3) is 3, Fibonnaci(4) is 5, and so on. Your function may only use a constant amount of memory (i.e. no auxiliary array). Argue that the running time of the function is Θ(n), i.e. the function is linear in n. 2. (10 points) Order the following functions by growth rate: N, \N,...

Java Match the sorting algorithm with its time complexity, where n is the number of elements...

Java Match the sorting algorithm with its time complexity, where n is the number of elements in the collection and k is the range of values. (This is a one-for-one match where an answer can only match one description.) Group of answer choices selection sort [ Choose ] O(n + k) O(n) to O(n^2) O(n log n) O(n^2) bubble sort [ Choose...
Consider the following description of an algorithm: first, sort the data. Then, search for the target...

Consider the following description of an algorithm: first, sort the data. Then, search for the target data element using binary search. If we assume that the sorting algorithm will take O(n2) time, what is the best big O estimate of the total algorithm time? O(log n) O(n^2 log n) O(n) O(n^2)
In C++ How do you demo that selection sort has O(N2) complexity? Meaning of the O(N2)....

In C++ How do you demo that selection sort has O(N2) complexity? Meaning of the O(N2). If you have N=1000 input values the selection sort need roughly 1000000 steps. What is the meaning of thee ‘step’ here? One ALU comparison, one swapping of values, or one calculation step on one value of the array. What is the total number of steps for selection sort? Let me use an example N=5, to help me think 4+1-__ 3+1-__ 2+1-__ 1+1-__ F(N)=__________________________ This...

fill in the blank Binary Search Tree AVL Tree Red-Black Tree complexity O(log N), O(N) in...

fill in the blank Binary Search Tree AVL Tree Red-Black Tree complexity O(log N), O(N) in the worst case O(log N) O(log N) Advantages - Increasing and decreasing order traversal is easy - Can be implemented - The complexity remains O(Log N) for a large number of input data. - Insertion and deletion operation is very efficient - The complexity remains O(Log N) for a large number of input data. Disadvantages - The complexity is O(N) in the worst case...
Provide an O(k log k) algorithm that uses a heap data structure to find the kth...

Provide an O(k log k) algorithm that uses a heap data structure to find the kth largest element from the heap of n elements where n > k. Sketch your algorithm. (Hint: You may need to use an additional heap) Use the example data below to demonstrate the process. (e.g. Find the 7 largest element from this heap and it should be 45) Justify the running time. Heap H 100 80 70 40 50 65 60 20 40 10 30...
2) (5 pts) An algorithm answers a query on a database of n elements in O(vn)...

2) (5 pts) An algorithm answers a query on a database of n elements in O(vn) time. For a database of size n= 10%, it takes 2 seconds to perform 5,000 queries. How many seconds should it take to answer 3,000 queries on a database of size n=108? (Note: all credit is based on the work and not the answer.)

(20 points) Recall the following deterministic select algorithm: (a) Divide the n elements into groups of...

(20 points) Recall the following deterministic select algorithm: (a) Divide the n elements into groups of size 5. So n/5 groups. (b) Find the median of each group. (c) Find the median x of the n/5 medians by a recursive call to Select. (d) Call Partition with x as the pivot. (e) Make a recursive call to Select either on the smaller elements or larger elements (de- pending on the situation); if the pivot is the answer we are done....