Time complexity of declaring an array in C++

Question

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.

To clarify, you are asking about the VLA extension that GCC provides? — UnholySheep
– UnholySheep, Commented Mar 8, 2018 at 12:15
This might be better posed as new int[len]. I'm pretty certain that automatic variable allocation will be O(1), dynamic might have a O(log(len)) feel to it if the OS needs to start thinking harder about paging &c. — Bathsheba
– Bathsheba, Commented Mar 8, 2018 at 12:16
I'm fairly sure if you look at the asm; it'll be O(1) ... if you have some more interesting objects though i'll be O(N) — UKMonkey
– UKMonkey, Commented Mar 8, 2018 at 12:18
@AlexKChen who knows - like I said; depends on Foo and what the compiler can optimise away. — UKMonkey
– UKMonkey, Commented Mar 8, 2018 at 12:22

Paul Floyd · Accepted Answer · 2018-08-27 10:40:37Z

5

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

edited Aug 27, 2018 at 10:40

answered Mar 8, 2018 at 12:28

Paul Floyd

7,1845 gold badges35 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Eduard Rostomyan · Accepted Answer · 2018-03-08 13:27:16Z

1

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).

answered Mar 8, 2018 at 13:27

Eduard Rostomyan

6,6664 gold badges45 silver badges91 bronze badges

1 Comment

user202729 Over a year ago

The OP is asking about VLA extension of GCC.

Collectives™ on Stack Overflow

Time complexity of declaring an array in C++

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related