Answer:
Explanation:
#include<iostream>
#include<ctime>
#include<bits/stdc++.h>
using namespace std;
double calculate(double arr[], int l)
{
double avg=0.0;
int x;
for(x=0;x<l;x++)
{
avg+=arr[x];
}
avg/=l;
return avg;
}
int biggest(int arr[], int n)
{
int x,idx,big=-1;
for(x=0;x<n;x++)
{
if(arr[x]>big)
{
big=arr[x];
idx=x;
}
}
return idx;
}
int main()
{
vector<pair<int,double> >result;
cout<<"Enter 1 for iteration\nEnter 2 for exit\n";
int choice;
cin>>choice;
while(choice!=2)
{
int n,m;
cout<<"Enter N"<<endl;
cin>>n;
cout<<"Enter M"<<endl;
cin>>m;
int c=m;
double running_time[c];
while(c>0)
{
int arr[n];
int x;
for(x=0;x<n;x++)
{
arr[x] = rand();
}
clock_t start = clock();
int pos = biggest(arr,n);
clock_t t_end = clock();
c--;
running_time[c] = 1000.0*(t_end-start)/CLOCKS_PER_SEC;
}
double avg_running_time = calculate(running_time,m);
result.push_back(make_pair(n,avg_running_time));
cout<<"Enter 1 for iteration\nEnter 2 for exit\n";
cin>>choice;
}
for(int x=0;x<result.size();x++)
{
cout<<result[x].first<<" "<<result[x].second<<endl;
}
}
Big-O notation is a way to describe a function that represents the n amount of times a program/function needs to be executed.
(I'm assuming that := is a typo and you mean just =, by the way)
In your case, you have two loops, nested within each other, and both loop to n (inclusive, meaning, that you loop for when i or j is equal to n), and both loops iterate by 1 each loop.
This means that both loops will therefore execute an n amount of times. Now, if the loops were NOT nested, our big-O would be O(2n), because 2 loops would run an n amount of times.
HOWEVER, since the j-loop is nested within i-loop, the j-loop executes every time the i-loop <span>ITERATES.
</span>
As previously mentioned, for every i-loop, there would be an n amount of executions. So if the i-loop is called an n amount of times by the j loop (which executes n times), the big-O notation would be O(n*n), or O(n^2).
(tl;dr) In basic, it is O(n^2) because the loops are nested, meaning that the i-loop would be called n times, and for each iteration, it would call the j-loop n times, resulting in n*n runs.
A way to verify this is to write and test program the above. I sometimes find it easier to wrap my head around concepts after testing them myself.
