Which of these two ways of algorithm analysis is right? What the difference between them?-CodePudding

I'm studying about algorithm analysis and to which Assympthotic class the algorithm belongs.

I found a simple exercise in internet with two resolutions and I don't know which of them is right, or if both are right, what is the difference between them?

RESOLUTION 1

Begin
  i = 0                 // O(1)
  While i <= n do:      // O(n)
    i = i   4           // O(1)
  print i               // O(1)
End

RESULT: This algorithm belongs to Θ = O(n).

RESOLUTION 2

Begin
  i = 0                 // 1
  While i <= n do:      // n
    i = i * 4           // 2n
  print i               // 1
End

RESULT: This algorithm belongs to Θ = 3n   2.

A - These two resolutions are right? If yes, what is the difference between them?

B - They have to count the 'print' too?

CodePudding user response：

I'm curious why, in Resolution 2, you marked the line i = i 4 as O(2n). Does that line of code take longer to run when n is higher? I don't think so - it appears that it would always take the same amount of time to run.

In general, something that is O(1) is something that always takes the same amount of time to run, regardless of the size of the input. For example, a statement line i = i n would take the same amount of time regardless of whether n was 1 or 1,000,000.

In general, something that is O(n) takes an amount of time that is directly proportional to n. So, if n was twice as large, it would take twice as long to run. Note that we are not saying that something that is O(n) always takes n steps. It might take 2*n steps, or 10*n steps, or n/2 steps, but it is always directly proportional to n. For example, your while loops fit this category. If n was twice as large, they would take twice as long to run.

So, there is no such thing as O(2n) or O(3n) or O(3n 2). All of those describe something that is directly proportional to n and so they would all be described as O(n).

Of course, there are other categories, like O(n^2) for things that are proportional to n squared, or O(log n) for things that are proportional to the logarithm of n, etc.

To be clear - this explanation is intended for a beginning student who is working on developing an intuition for how to think about big-O style analysis. A more advanced student learning about big-omega, big-theta, etc., would need much more nuanced definitions.