CODEWITHSUNDEEP
algorithmtime-complexity
jMan
jMan

Reputation: 637

How do I count primitive operations in this algorithm?

Firstly: What is the T(n), and thus O(n) of the following Pseudo-Code? How can I go through and count operations for code like this when the inner for-loop has a variable limit?

Secondly: What are the primitive operations to look for as I am struggling to count them exactly.

I understand it isn't necessary to count the exact number of primitive operations (for O(n)) but knowing how to do so that would make me more comfortable calculating the 'big picture'.

Input: X, a 1-D numerical array of size n
1) Let A = an empty 1-D numerical array of size n ~T1 = 1 or n  
2) For i = 0 to n-1                               ~T2 = n (multiplies T3 to T8)                     
3)    Let s = X[0]                                ~T3 = 1                     
4)    For j = 1 to i                              ~T4 = ? multiplies T5                     
5)       Let s = s + X[j]                         ~T5 = 2 reads and 1 set? Or 1 operation if using +=?                     
6)    End For                                     ~T6 = 0                   
7)   Let A[i] = s /(i+1)                          ~T7 = 1 set and 1 or 2 reads                     
8) End For                                        ~T8 = 0  
Output: An n-element array A of numbers such that A[i]
        is the average of elements X[0],X[1], … ,X[i]

Any materials/resources/Qs that sharpen primitive operation counting (with answers) are greatly appreciated.

Upvotes: 0

Views: 12106

Answers (2)

jMan
jMan

Reputation: 637

So it seems the easiest way to break this problem down is by working out the total for each line immediately, rather than multiplying afterwards. The clarifications are:

  • T1 Setting an array of any size is 1 operation
  • T2 The setting of a For loop is the range of i: n
  • T3 1 read plus 1 set times n, 2n
  • T4 Using the logic of the first for loop on the secondary one and counting towards a small n instead of trying to multiply immediately, we see we'd have 0 (discounted because for j=1 to 0 makes no sense) + 1+2+...+(n-1). Now we use the famous Sum formula Sx=x(x+1)/2 except here we're using n-1 so Sn-1 = (n-1)(n-1+1)/2 = (n2 - n)/2
  • T5 is read+read+add+set, 4 operations, times it's immediate for loop giving 2(n2-n)
  • T6 is 0 as it's just marking the end of the for loop
  • T7 can be guessed (not certain) as going left to right: set+read+divide+read+add, 5 operations, times the outside for loop's size which means 5n
  • T8 see T6

THUS adding Tn for 1 to n gives us the unattractive:

T(n) = 1 + 5.5n + 2.5n2

O(n2)

TL;DR: work out each line individually, use sum of first n natural numbers formula, use small n if too difficult to do in abstract.

Initially this confused me as I was working with non-integer coefficients for T(n), but the result is always an Integer :)

Upvotes: 1

user1196549
user1196549

Reputation:

I would count separately the reads/writes to an array, the arithmetic operations and the number of for loop iterations.

In the inner loop (4-6), i reads, i +, i for.

Then in the outer loop (2-8), n reads, n inner loops (i=0 to n-1), n +, n /, n writes, n for.

In total, (n+1)n/2 reads, n writes, (n+1)n/2 +, n /, (n+1)n/2 for.

I am counting these separately because their execution time can be highly architecture dependent and also data-type dependent. Other operations, such as moves of local data (held in register) are somehow absorbed in the former.

Clearly, for large n (say >25) the reads, accumulations and loops dominate. For very large n, due to cache effects, you can expect the reads alone to dominate.

Upvotes: 0

Related Questions