CODEWITHSUNDEEP
c++time-complexity
katana_0
katana_0

Reputation: 183

Time complexity of declaring an array in C++

What's the time complexity of the following code in C++: (note that I'm using gcc, so len is taken as an input from the user)

int array[len]; \\array is uninitialized

Is it O(1) or O(len) ? I am a bit confused.

Upvotes: 2

Views: 1861

Answers (2)

Paul Floyd
Paul Floyd

Reputation: 6906

In general for POD types the time will be O(1).

If you have user defined constructors (or destructors, I assume that the time taken to release the resources should also be considered) then I would expect the time complexity to be O(n).

If you can wait a little, I submitted an article to Overload on the code size and execution time required for objects that are allocated automatically and dynamically. I'm expecting it to be out this April.

Update: Here is the link for the published Overload article No news is good news

Upvotes: 5

Eduard Rostomyan
Eduard Rostomyan

Reputation: 6546

The general rule:

type name[size];

If your type is Plain Old Data (POD) than compiler can invoke allocation and construction in O(1).
Otherwise en explicit constructor call is required for each entity which is O(n).

Upvotes: 1

Related Questions