How to reduce Execution time ?? Should I use functions or remain with the idea of nested loops

Question

I have to reduce execution time in this code. In this problem the value of n may go upto 10^8 . And hence i think nested loops are not that good because it is very laggy for large data's . So I was wondering if I use a function instead of the inner loop . Will this idea work for reduction of execution time?? or it will be the same case even if i use funtions??

#include <stdio.h>
long long a[500001]={0};
int main()
{
long long n,i,j,flag,sum=0,temp,count=0;

scanf("%lld",&n);
for(i=0;i<n;i++)
    scanf("%lld",&a[i]);
for(i=0;i<n;i++){
    for(j=0;j<n;j++)
    if(a[j]>=a[i])
        count++;
     flag=a[i]*(count);
     if(flag>sum)
        sum=flag;
     count=0;
}
printf("%lld",sum);
return 0;
}

You should use *more efficient algorithm* and it may not depend on functions. — MikeCAT, Mar 06 '16 at 14:39
If `n` goes up to 100,000,000 why have you declared a with a lower number? — Ed Heal, Mar 06 '16 at 14:39
Functions and loops are different constructs for different problems. You are comparing apples and bananas (oranges are still too close to apples - both are round). — too honest for this site, Mar 06 '16 at 14:44
and why do i get so many negatives for this question was this a stupid doubt?? — user5910213, Mar 06 '16 at 14:55
Please describe conceptually what this code is supposed to do. Then someone might be able to suggest a better way. — dbush, Mar 06 '16 at 15:28

ganchito55 · Answer 1 · 2016-03-06T21:25:34.790

1

I think that your problem is the algorithm:

for(i=0;i<n;i++){
for(j=0;j<n;j++)

You have here O(n^2), so this is very complex algorithm.

Can you explain what do you want to get with that code?

An improved solution

1) sort your data from higher to lower value O(n) or O(n*log(n))
2) Use this algorithm:

 int max=0,tmp=0;
 for(i=0;i<n;i++){
      tmp=array[i]*(i+1);
      if(max<tmp) max=tmp;
  }

Example

Input: 4 30 20 53 14

1) Array = {53,30,20,14,4}
2)

    tmp     | max | iteration  
    0       |0    | 0  
    53      |53   | 1  
  30*2=60   |60   | 2  
  20*3=60   |60   | 3  
  14*4=56   |60   | 4  
  4*5=20    |60   | 5

Output:60

Complexity

if sort is O(nlog(n)) and my algorithm is O(n) you get an O(nlog(n)) complexity.

edited Mar 06 '16 at 21:25

answered Mar 06 '16 at 17:46

ganchito55

3,559
4
25
46

How do you find complexity . Can you suggest a website from where i can learn to find complexity. or you can tell it here? – user5910213 Mar 07 '16 at 03:56
But BTW your solution may take more time cause you need to first sort the data and then you will find the sum . This may take more time i think so what are your opinions? – user5910213 Mar 07 '16 at 07:11
1

@user5910213 [here](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) you can find information about time complexity. When you use Big o (O), you only have to get the slowest operation. Because if you have two operations, one O(n) and the other O(n^2), when n takes large values, n<<<< – ganchito55 Mar 07 '16 at 10:03
I am saying that will your code not take too much time because you need to sort the elements first then further – user5910213 Mar 12 '16 at 11:12

How to reduce Execution time ?? Should I use functions or remain with the idea of nested loops

1 Answers1

An improved solution

Example

Complexity