Asymptotic Time Complexity


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
Copy the contents of the old array into the new one
If the record already exists
Update the record
Else
Create a new record and add it to the array
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.

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. Thus
with this "factored out", what we have is linear or O(n) asymptotic
time complexity.

Does this make any sense?

Thanks a lot!

.

Relevant Pages

  • Re: Lowest array value given index
    ... Jim wrote: ... > array but starting at a given index. ... My suggestion above is not efficient with respect to time complexity, ... Fort Worth, Texas ...
    (comp.lang.perl.misc)
  • Re: efficient search on the array
    ... the same with time complexity as the priority, ... a is an array of integers having combination of 0 and 1 only. ... when number of 1s in any one of the set of 1's is odd. ...
    (comp.lang.c)
  • Re: manually sort array of numbers
    ... quadratic fashion. ... while the built in sort follows n * log ... Why do we say that yours is Oinstead of some other time complexity? ... So that is the first n, it goes through each of the n indexes in the array. ...
    (comp.lang.ruby)
  • Re: efficient search on the array
    ... the same with time complexity as the priority, ... a is an array of integers having combination of 0 and 1 only. ... when number of 1s in any one of the set of 1's is odd. ... You have parity-check problem. ...
    (comp.lang.c)
  • 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)