Thread: Analysis of algorithm

Can some one tell me if i am doing i right

a function 23n^2 operation for input size n.

1) how many operation per second would your computer have to do in order to complete an input size 100 in 10 minutes ?

2) Assume the computer does 50000 operation in a second. what is the largest amount of input that can be done in an hour?

Solutions

1) 10 min = 600 sec
23(100)^2 = 230,000
230,000/600 = 383 operation

2) 50,000 opr in a second = 50,000/1,000,000 = 1/20
3600/20 = 180

please help

Hey hatol25.

You have the right idea for the first one except that you rounded your answer down. If you re-check your answer with 600*383 you get 229800 which is less than 230000, so you have to round up and add an extra cycle to gaurantee that it will finish in that time (even though it will finish slightly quicker).

For the second one you need to look at the total number of operations in an hour. There are 3600 seconds in an hour (60 seconds per minute and 60 per hour) which means the total number of operations in one hour is 50,000*3,600 = 180,000,000 or 180 million.

So now we have to find a value of n where 23*n^2 = number of operations, but we found this to be 180 million (or 180,000,000). So 23n^2 = 180,000,000. What does this imply about our size n?