Examveda

What will be the time complexity of the following code?
#include <bits/stdc++.h> 
using namespace std; 
 
int min(int x, int y) 
{ return (x < y)? x: y; } 
 
int func(int arr[], int n) 
{ 
 
	int *jump = new int[n]; 
	int i, j; 
 
	if (n == 0 || arr[0] == 0) 
		return INT_MAX; 
 
	jump[0] = 0; 
 
	for (i = 1; i < n; i++) 
	{ 
		jump[i] = INT_MAX; 
		for (j = 0; j < i; j++) 
		{ 
			if (i <= j + arr[j] && jumps[j] != INT_MAX) 
			{ 
				jump[i] = min(jump[i], jump[j] + 1); 
				break; 
			} 
		} 
	} 
	return jump[n-1]; 
} 
 
int main() 
{ 
	int arr[] = {1, 3, 6, 1, 9,7}; 
	int size = sizeof(arr)/sizeof(int); 
	cout<< func(arr,size); 
	return 0; 
}

A. O(n log n)

B. O(n)

C. O(n1/2)

D. O(n2)

Answer: Option D


This Question Belongs to Data Structure >> Arrays In Data Structures

Join The Discussion

Related Questions on Arrays in Data Structures