The Student Room Group
Uni students - Complete our survey >>
Uni students - Complete our survey >>
Uni students - Complete our survey >>

Algorithm efficiency and the Big O notation

Any one here understand how to answer the following question?

ALGORITHM A-

SET sum TO 0
FOR i=1 to size
FOR j= 1 to 10000
sum = sum + i

ALGORITHM B

SET sum TO 0
FOR i=1 to size
FOR j=1 to size
sum = sum +1

(computer performs 1 million operations per second)


Any idea how how long will it take for each of the algorithms to solve a problem with size of one million operations? and what happens If the size of the problem is doubled to TWO million operations in relation to time requirement?
Original post by BiologyBlooper
Any one here understand how to answer the following question?

ALGORITHM A-

SET sum TO 0
FOR i=1 to size
FOR j= 1 to 10000
sum = sum + i

ALGORITHM B

SET sum TO 0
FOR i=1 to size
FOR j=1 to size
sum = sum +1

(computer performs 1 million operations per second)


Any idea how how long will it take for each of the algorithms to solve a problem with size of one million operations? and what happens If the size of the problem is doubled to TWO million operations in relation to time requirement?

Lets do each line 1 by 1, I assume these are nested loops

ALGORITHM A-

SET sum TO 0 Constant (1)
FOR i=1 to size N
FOR j= 1 to 10000 Contant (1)
sum = sum + i Contant (1)

Hence total run time = 1*n*(1*1) hence as we increase the amount of data i.e increasing n, the run time approaches n hence we say the run time of the algorithm is o(n) worse case scenera. Best case scenario n is just 1 so the run time is now O(1)

ALGORITHM B

SET sum TO 0
FOR i=1 to size
FOR j=1 to size
sum = sum +1
Reply 2
Avatar for JickDee
JickDee
13
Original post by BiologyBlooper
Any one here understand how to answer the following question?

ALGORITHM A-

SET sum TO 0
FOR i=1 to size
FOR j= 1 to 10000
sum = sum + i

ALGORITHM B

SET sum TO 0
FOR i=1 to size
FOR j=1 to size
sum = sum +1

(computer performs 1 million operations per second)


Any idea how how long will it take for each of the algorithms to solve a problem with size of one million operations? and what happens If the size of the problem is doubled to TWO million operations in relation to time requirement?


Algorithm A is O(n). Algorithm B is O(n^2)
So when you double the size, algorithm A's time doubles and algorithm B's time quadruples.

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you