Member Avatar for jaiop 
{
SumOddEven(A,n)             //A is array and n is size of array
{
    int count, sum;
    for(int i = 1; i<=n; i++)  {
    sum_even=0;
    sum_odd=0;
                    for(int j = i; j<=n; j++)  {
               if (A[j] Mod 2 == 0)                  //check if number is even
                                        sum_even=sum_even+A[j]    //Sum even numbers
                                    else
                                        sum_odd=sum_odd+A[j]      //Sum odd numbers
              }
    cout<<sum_even;
    cout<<sum_odd;
            }
}
  • 5 Contributors
  • 4 Replies
  • 324 Views
  • 1 Week Discussion Span
  • Latest Post Latest Post by dannyniu

Dani AI

Generated

This does work out to quadratic time. The outer loop runs n times and for each i the inner loop runs from i to n, so the inner body executes

sum_{i=1..n} (n - i + 1) = 1 + 2 + ... + n = n(n+1)/2

times — about n^2/2. Each inner iteration does constant work (parity test, one addition and a branch), so the overall running time is Theta(n^2) (equivalently O(n^2) and Omega(n^2)).

A few practical notes: resetting the two sum variables at the start of each outer iteration and printing the two results once per outer iteration are both constant-time per iteration, so they do not change the quadratic dominating term. If you treat console I/O as expensive, the n prints add an extra O(n) cost, but that is still lower order compared to n^2 for large n. The extra memory used is constant (O(1)).

To check reasoning: count the if executions (as recommended) — you get n(n+1)/2. That directly contradicts ’s guess of linear time. ’s tip to use the time command is useful for measuring real runtime, but empirical timing does not replace the asymptotic analysis above. Indexing convention (1-based vs 0-based) or small implementation details do not change the Theta(n^2) result.

Recommended Answers

All 4 Replies

Member Avatar for rch1231

Under Linux you can use the time command to give you the amount of time taken to run a command. To review the manual entry for time use:
man time

TIME(1)                       Linux User's Manual                      TIME(1)

NAME
       time - time a simple command or give resource usage

SYNOPSIS
       time [options] command [arguments...]

DESCRIPTION
       The  time  command  runs  the  specified program command with the given
       arguments.  When command finishes, time writes a  message  to  standard
       error  giving  timing statistics about this program run.  These statis‐
       tics consist of (i) the elapsed real time between invocation and termi‐
Member Avatar for Gribouillis

Compute how many times the if statement is executed.

Member Avatar for Dean_williams

Did you face a problem or an error in the code given?

If you did, post the error noted here for us to provide our perspective on the problem.

If you want to get an understanding on measuring time complexity, you can refer to the post i have made earlier that relates to this problem at the below link:-
Click Here

Member Avatar for dannyniu

I suppose it has a run time linear to the size of the input n. I'm no expert on computational complexity, but I've heard some of the concepts.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.