72016

Average Case Time Complexity Analysis of Binary Counter Increment

I am attempting to find the average case time complexity, not amortized analysis, of a binary counter. As I am not entirely confident in my time complexity analyzing skills, I would like to confirm that my average case analysis of the pseudocode provided below is correct.

Let k be the length of the array.

Increment(Array) i = 0 while i < k and Array[i] == 1 Array[i] = o i = i + 1 if i < k Array[i] = 1

In order to find the average time taken, I find the average amount of bits flipped per run. As a result, I found this to be O(2+k/(2^k)), which equals O(1) for a large k.

Is this the correct average case running time? If not, how would I begin to approach this problem?

Answer1:

I am assuming each input has the same probability to occur

This means that each bit is independently on or off with probability 1/2.

The geometric distribution is the relevant distribution for the complexity: you flip coins, and end the experiment on the first tail outcome (there is nothing further to carry).

The mean of the geometric distribution here is exactly 2 (see above link, or derive it from basic principles), so the average complexity is indeed O(1).

Recommend

  • Placing coordinates on a map - Python
  • Issue drawing multiple Images on Canvas with drawImage()
  • Load and display an image: why is it rotated 90°? [duplicate]
  • Matlab Image and Plot with Unexpected Flip
  • Selection sort growing ordered ranges from both ends
  • Mutate value by using a value from a different row in a tibble
  • longest common subsequence: why is this wrong?
  • Inno Setup Search for specifc file on a CD, retrieve exact filepath and return value to [Files]-Sect
  • ProgressBar Paint Method?
  • datatables left join c#
  • C: Custom strlen() library function
  • Nginx rewrite equivalent to Apache RewriteRule that converts URL params into QueryString key/value p
  • Can't connect Entity Framework to local SQL Server Express
  • How to extract a number from a string [duplicate]
  • How to synchronize jQuery dialog box to act like alert() of Javascript
  • DIV instruction jumping to random location?
  • Updating both a ConcurrentHashMap and an AtomicInteger safely
  • C# program and C++ DLL compiled for 32-bit system crash on 64-bit system
  • Web.config system.webserver errors
  • Z3: Convert between FP and BitVector?
  • Jackson Parser: ignore deserializing for type mismatch
  • Initializer list vs. initialization method
  • C# - Is there a limit to the size of an httpWebRequest stream?
  • Date difference with leap year
  • Statically linking a C++ library to a C# process using CLI or any other way
  • Function pointer “assignment from incompatible pointer type” only when using vararg ellipsis
  • Rearranging Cells in UITableView Bug & Saving Changes
  • 0x202A in filename: Why?
  • SVN: Merging two branches together
  • Hibernate gives error error as “Access to DialectResolutionInfo cannot be null when 'hibernate.
  • retrieve vertices with no linked edge in arangodb
  • Benchmarking RAM performance - UWP and C#
  • Angular 2 constructor injection vs direct access
  • FormattedException instead of throw new Exception(string.Format(…)) in .NET
  • How to CLICK on IE download dialog box i.e.(Open, Save, Save As…)
  • Change div Background jquery
  • Can Visual Studio XAML designer handle font family names with spaces as a resource?
  • File not found error Google Drive API
  • IndexOutOfRangeException on multidimensional array despite using GetLength check
  • apache spark aggregate function using min value