Re: Asymptotic Time Complexity


On Fri, 26 Jan 2007 s_valmont@xxxxxxxxx wrote:

Just wondering if my time complexity analyis of the algorithm below is
accurate as I am new to this! The algorithm involves storing data
using an array and afterward printing it sorted.

<algorithm>

For each line of data we receive
If the record count plus one is larger than the array size
Create a new, bigger array

Until you figure out how much bigger is "bigger", this is not
an algorithm, it's just an outline. Is the "bigger" array one
element bigger? Two elements? Twice as big as the old one? Five
times as big? Big squared?

Copy the contents of the old array into the new one
If the record already exists

How do you find out if a record already exists? That step might
take O(1), O(lg N), or even O(N), depending on your data structures.

Update the record
Else
Create a new record and add it to the array

At the end of the array, I presume. If you add it to the beginning,
or somewhere in the middle, you're going to have to shift all the
other elements up by one, and that will take time.

Increase the record count

Sort the array

For each record in the array
Print the record

</algorithm>

All steps are constant or linear time complexity except for one
sequence - when we need to resize our array.

And sorting, of course, which is O(N lg N).

However the large amount of time required by the resizing operation is
amortized constant time due to the fact that it is averaged over the
relatively large number of cycles that do not require a resize.

What makes you think the number of steps without a resize is
"relatively large"? And what exactly do you mean by "relatively"?
Do you mean that the number of steps requiring a resize is 10% of
the total; or 1/N of the total; or 1/(2**N); or what?

Thus with this "factored out", what we have is linear or O(n) asymptotic time complexity.

It's got to be at least O(N lg N) because of the sorting step.
Beyond that, it depends on your answers to the questions I asked.

HTH,
-Arthur
.

Relevant Pages

  • Re: regex question - trying to find ".mp3" in a SELECT box
    ... But `Array' is a Function object reference. ... Establish a new execution context using F's FormalParameterList, ... Since is not a primitive value, the exception should be thrown. ... | 5.2 Algorithm Conventions ...
    (comp.lang.javascript)
  • Re: Mergesort Vs Quicksort
    ... I might not have correctly remembered my algorithm of months ago ... for sorting records in an array using one auxilary of the ... on how things turn out from lower levels of recursion, ... whether the number of records in the array segment to be sorted is ...
    (comp.programming)
  • Re: Reference to derived type element by index?
    ... as a set of distinctively-named scalars. ... In another scope, the same common block ... would be a single array. ... algorithm and a specific application of the algorithm, ...
    (comp.lang.fortran)
  • [SUMMARY] Maximum Sub-Array (#131)
    ... # sum the integer values of array contents ... algorithm, ... all possible lengths, to check each subarray. ... $ time ruby -r max_sub_array ...
    (comp.lang.ruby)
  • Re: counting subsets of S so that sum(S_n) = N
    ... and make my algorithm generate only unique subsets? ... and the array of boolean at one step of the algorithm is ... implementation without needing recursion. ... subsequence in W, process it and return. ...
    (comp.programming)