What is the space complexity of this function / algorithm?int **allocate_map(int n, int m){ int **map; map = malloc(sizeof(int *) * n); for (size_t i = 0; i < n; i++) { map[i] = malloc(sizeof(int) * m); } return (map);}O(1)O(nm)O(n^2)O(log(n))I don't knowSubmit

What is the time complexity of this function / algorithm?void f(int n){ int i; for (i = 0; i < n; i++) { printf("[%d]\n", i); }}O(n)O(1)O(log(n))O(nlog(n))O(2^n)O(n!)O(n^2)

What is the space complexity of Heap Sort?

What is the time complexity of this function / algorithm?void f(unsigned int n){ int i; for (i = 1; i < n; i = i * 2) { printf("[%d]\n", i); }}

What is the time, space complexity of following code : int a = 0, b = 0; for (i = 0; i < N; i++) { a = a + rand(); } for (j = 0; j < M; j++) { b = b + rand(); }Assume that rand() is O(1) time, O(1) space function.

What is the worst case time complexity of the following code :/* * V is sorted * V.size() = N * The function is initially called as searchNumOccurrence(V, k, 0, N-1) */int searchNumOccurrence(vector<int> &V, int k, int start, int end) { if (start > end) return 0; int mid = (start + end) / 2; if (V[mid] < k) return searchNumOccurrence(V, k, mid + 1, end); if (V[mid] > k) return searchNumOccurrence(V, k, start, mid - 1); return searchNumOccurrence(V, k, start, mid - 1) + 1 + searchNumOccurrence(V, k, mid + 1, end);}NOTE : This question involves recursion which will be explained later in topic Backtracking. So, if you are not able to approach this question now, you can give it a try later.