How the time complexity is O(N^2)?

#1

I ran the given code with vector of 6 elements.


When I call the recursive function, I clearly see only N i.e 6 calls are made.


Please refer to the image and explain how the time complexity is O(N^2)).

801×605 36 KB

#2

Hey @thirumeni.m07
Its N^2 because vector is passed by value
So for each recursive call its copied to another vector

So for N calls vector of size N is copied
=> N^2

1 Like
#3

Hi Kartik, it’s question 9 : Which of the following can be used to store a simple undirected graph with N nodes?

#4

vector < int > graph [ N + 1 ]

bool graph [ N + 1 ][ N + 1 ]

vector < vector < int > > graph(N+1)

All of them.

#5

1st and 3rd option can be used to create graph as adjacenecy list
And 2nd option as adjacenecy matric

#6

So as per option 1 every node can have just one adjacent node because it’s a one dimensional vector?

#7

No
1st option means we have created N vectors
And every vector can have variable no of elements.

Int arr[N]. Means we have created N integers
Similarly that means we have created N vectors

1 Like