CODEWITHSUNDEEP
algorithmtime-complexitybig-opseudocode
Luke Collins
Luke Collins

Reputation: 1463

Determining the number of steps in an algorithm

I was going through my Data Structures and Algorithms notes, and came across the following examples regarding Time Complexity and Big-O Notation: Example 1 Example 2 Example 3 The columns on the left count the number of operations carried out in each line. I didn't understand why almost all the lines in the first example have a multiple of 2 in front of them, whereas the other two examples don't. Obviously this doesn't affect the resulting O(n), but I would still like to know where the 2 came form.

Upvotes: 0

Views: 4340

Answers (1)

Salvador Dali
Salvador Dali

Reputation: 222849

I can only find one explanation for this: the sloppiness of the author of the slides.

In a proper analysis one have to explain what kind of operations are performed at which time for what input (like for example this book on page 21). Without this you can not even be sure whether we count multiplication of 2 numbers as 1 operation or 2 or something else?

These slides are inconsistent. For example:

In slide1 currentMax = A[0] takes 2 operations. Kind of makes sense if you take finding 0-th element in array as 1 operation and assigning as another one. But in the slide3 n iterations of s = s + X[i] takes n operations. Which means that s = s + X[i] takes 1 operation. Also kind of makes sense we just increase one counter.

But it is totally inconsistent with each other, because it doesn't makes sense that a = X[0] is 2 operations, and a = a + X[0] where you do more takes only 1.

Upvotes: 1

Related Questions