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;
}
#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

Join The Discussion