Suppose that a computer can run an algorithm on a problem of size 1,024 in time t. We do not know the complexity of the algorithm. We note that when we run the same algorithm on a computer 8 times faster, in the same time t, we can solve a problem of size 8,192. We also note that when we run the same algorithm on a computer 8 times slower, in the same time t, we can solve a problem of size 128.

Question

Computers and Technology

Leah

7 February, 13:57

Suppose that a computer can run an algorithm on a problem of size 1,024 in time t. We do not know the complexity of the algorithm. We note that when we run the same algorithm on a computer 8 times faster, in the same time t, we can solve a problem of size 8,192. We also note that when we run the same algorithm on a computer 8 times slower, in the same time t, we can solve a problem of size 128.

+4

Answers (1)

Know the Answer?

Lawson Fleming · Answer 1

Time Complexity of Problem - O (n)

Explanation:

When n = 1024 time taken is t. on a particular computer.

When computer is 8 times faster in same time t, n can be equal to 8192. It means on increasing processing speed input grows linearly.

When computer is 8 times slow then with same time t, n will be 128 which is (1/8) th time 1024.

It means with increase in processing speed by x factor time taken will decrease by (1/x) factor. Or input size can be increased by x times. This signifies that time taken by program grows linearly with input size n. Therefore time complexity of problem will be O (n).

If we double the speed of original machine then we can solve problems of size 2n in time t.