0
$\begingroup$

I'm studying for a computing exam and came past the following question on a past paper and need help with it.

When would algorithm A be slower than algorithm B? Demonstrate your answer with the help of an example. Also what will the value of SUM be at the end of each algorithm if the size is set to $10'000$?

Algorithm A:

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

Algorithm B:

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

I came up with this answer but not sure if it is correct:

The algorithm A will be slower than algorithm B when the performance of the algorithm is directly proportional to the cubed or more of the size of the input data set, for example if the Big O notation becomes $O(N^3)$ or $O(N^4)$ or $O(N^5)$ etc. The Big $O$ notation $O(N^3)$ nesting the for loops in two more for loops:

Set Sum TO 0
For i=1 to size
  For k=1 to size
    For l=1 to size
      For j=1 to 10000
sum=sum+1
|cite|improve this question
$\endgroup$
  • $\begingroup$ just count for each algo how much times sum+=1 will be executed $\endgroup$ – Bulat Jul 9 at 22:05
  • $\begingroup$ @bulat what do you mean? can you elaborate? $\endgroup$ – donk2017 Jul 9 at 22:51
  • $\begingroup$ well, let's simplify it a bit - FOR i=1 TO 100 DO SUM+=1 - how much times sum+=1 operation will be performed? $\endgroup$ – Bulat Jul 9 at 23:14
  • $\begingroup$ @bulat 100 times $\endgroup$ – donk2017 Jul 9 at 23:15
  • 1
    $\begingroup$ Your answer makes no sense, sorry. The question asks you to compare two specific algorithms but your answer talks about a thirs algorithm that's completely different from both of them. $\endgroup$ – David Richerby Jul 10 at 9:19
1
$\begingroup$

Algorithm A contains an instruction that is executed $size * 10000$ times.
Algorithm B contains an instruction that is executed $size * size$ times.

It is obvious that the comparison between A and B depends on the variable size.
You can see that if $size < 10000$ then B performs better, and if $size > 10000$ then A performs better.
If $size = 10000$ then A and B can be considered equally fast.

It is easy to calculate the result for $sum$ when $size = 10000$.

I am not sure if it makes sense to answer with big O notation here because the algorithms are different. A computes $size * 10000$ and B computes $size^2$, which are two different algorithms; it does not make sense to compare them with big O notation in my opinion. Usually big O analysis helps in comparing algorithms that solve the same problem, which is not the case here.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ in many cases we need to compare two algos doing different things, for example two steps of larger algo so we can find the slower part. In this particular case, we can imagine that increment operations just represent steps of actual algorithms such as radix and bubble sort $\endgroup$ – Bulat Jul 10 at 11:38
0
$\begingroup$

The question is posed badly.

The asymptotic execution time of one algorithm is $\Theta(n^2)$, the other is $\Theta(n)$. That means A is asymptotically faster on any implementation.

But that’s not the question. The question is “when is A faster”. And that depends on the exact implementation. We can make an educated guess: Both algorithms add up the same number of integers when size=10,000. But what the exact execution time is, we can only guess.

PS. Many compilers will replace the inner loop with “sum=sum+10,000” or “sum=sum+size” and the question changes totally. Many compilers will calculate the sum in constant time.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ for us it's obvious that both algos will be optimized to the single instruction, and (for me) it seems obvious that the question supposed that each sum+=1 operation takes constant time $\endgroup$ – Bulat Jul 10 at 11:36
  • $\begingroup$ If a question supposes something that is not true then it is badly posed. $\endgroup$ – gnasher729 Jul 10 at 18:14

Not the answer you're looking for? Browse other questions tagged or ask your own question.