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.
Asked
Active
Viewed 1,529 times
2
-
1To clarify, you are asking about the VLA extension that GCC provides? – UnholySheep Mar 08 '18 at 12:15
-
3This 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 Mar 08 '18 at 12:16
-
@UnholySheep I have no idea (I am new to c++). I just simply use codeblocks with mingw and I can create an dynamic array. – katana_0 Mar 08 '18 at 12:18
-
1I'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 Mar 08 '18 at 12:18
-
1What is `len` defined as? – Paul Floyd Mar 08 '18 at 12:19
-
Bonus question: what about `Foo array[len]` where `Foo` is a struct defined by me ? – katana_0 Mar 08 '18 at 12:19
-
@AlexKChen Well that depends on Foo now doesn't it. – UKMonkey Mar 08 '18 at 12:20
-
@UKMonkey Yeah, so I mean is it then `O(sizeoff(Foo)*len)` or `O(sizeof(Foo))` or anything else ? – katana_0 Mar 08 '18 at 12:21
-
1@AlexKChen who knows - like I said; depends on Foo and what the compiler can optimise away. – UKMonkey Mar 08 '18 at 12:22
-
1I suspect it is more like O(0) – Galik Mar 08 '18 at 12:28
-
This only works for `len` reasonably small, and only as an extension to C++ – Basile Starynkevitch Mar 08 '18 at 12:31
-
Anyway, variable length arrays do not exist in C++, they are only allowed by a gcc extension. – Serge Ballesta Mar 08 '18 at 12:45
-
@4386427 I think the OP is just curious. – user202729 Mar 08 '18 at 13:17
-
[Related](https://stackoverflow.com/questions/161053/which-is-faster-stack-allocation-or-heap-allocation). – user202729 Mar 08 '18 at 13:19
2 Answers
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
Paul Floyd
- 5,530
- 5
- 29
- 43
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).
Eduard Rostomyan
- 7,050
- 2
- 37
- 76