Is my Time Complexity Analysis right? The counting I did are right?-CodePudding

I want to count how many instructions are executed in the follow algorithm.

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

So.. 3n   2?

Is 3n 2 right for this exercise? The print is counted?

CodePudding user response：

As currently written,

If n ≥ 0:

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

If n < 0:

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

Now, I suspect i should be initialized to 1. In this case, for n → ∞:

Begin
  i = 1                 // θ(1)
  While i <= n do:      // θ(log(n))
    i = i * 4           // θ(log(n))
  print i               // θ(1)
End

The loop takes θ(log(n)) steps, because i takes exponentially larger strides towards n:

 1, 4, 16, 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576, ...

Note, that I used theta notation (θ), instead of specific "instruction count", as you can't know in general case how many "instructions" each high level statement corresponds to. That's why the whole family of asymptotic notations omit constants, i.e. O(c₁ n c₂) = O(n).