time complexity of program when 2D array is initialised?

Question

#include <iostream>
using namespace std;
int main()
{
    int a[100][100]={10};
    cout<<a[0][0];
    return 0;
}

what is the time complexity of above program? is it O(1) or O(100^2)??

Initializing an array that way is done by the compiler at time of compilation, so it's O(1) during run-time. — Some programmer dude
– Some programmer dude, Commented Feb 6, 2015 at 7:47
The above code does not set all element to 10. Only a[0][0] will be 10 — Thiyagu
– Thiyagu, Commented Feb 6, 2015 at 7:49
To clarify: there is nothing in your code that can change. There's no N in it. It will always run the same thing. So, O(1). — juanchopanza
– juanchopanza, Commented Feb 6, 2015 at 7:56

Jarod42 · Accepted Answer · 2015-02-06 08:26:02Z

4

Initializing an array is O(N).
O(k) == O(1) (for constant k, k > 0).

As your array have fixed size, the complexity of the program is O(1).

if you change your program to something like:

#include <iostream>
#include <vector>
int main()
{
    int size;
    std::cin >> size;
    std::vector<int> a(size);
    // ..
}

There, the initialization of a is O(N).

answered Feb 6, 2015 at 8:26

Jarod42

227k15 gold badges214 silver badges349 bronze badges

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

Comments

CiaPan · Accepted Answer · 2015-02-06 08:08:06Z

1

All values in your code are constant, so its execution time is constant: O(1).

(Of course the actual time depends on the machine you choose to run the program as well as on unpredictable external conditions, like the overall system load at the execution time.)

answered Feb 6, 2015 at 8:08

CiaPan

9,5802 gold badges23 silver badges38 bronze badges

Comments

Mohsin · Accepted Answer · 2015-02-06 07:50:01Z

0

Time complexity is constant because consider allocating space with malloc(sizeof(int)*rows*cols) where rows and cols have been defined before.

Also, the array indexing happens in constant time. Therefore, overall it is constant.

answered Feb 6, 2015 at 7:50

Mohsin

5566 silver badges19 bronze badges

Collectives™ on Stack Overflow

time complexity of program when 2D array is initialised?

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related