433 views
3 votes
3 votes
What is the Time and Space Complexity of Both the Codes ? Are both O(1)? If so why? And then how is the second more efficient?

Below is the code in Brute Force

for(i=0;i<1000;i++)
    {
        if(i%3==0 || i%5==0)
        {
            sum+=i;
        }
    }

This is Using Summation

int P1(int n)
{
    int t,x,f;
    t=(n-1)/3;
    x=(n-1)/5;
    f=(n-1)/15;
    return((3*t*(t+1)/2) + (5*x*(x+1)/2) - (15*f*(f+1)/2));
}

1 Answer

Best answer
2 votes
2 votes
Indeed. Asymptotically both are O(1), as the time taken is independent of input size (n).

However, the number of comparisons in the first case is a lot more than the second case (actually there's no comparison at all in the second case), thus the constant factor is larger in the first case. So second one is more efficient.

By the way, as far as i remember, this is the 'Multiples of 3 and 5' problem on ProjectEuler+.
selected by

Related questions

0 votes
0 votes
3 answers
1
Nisha Bharti asked Sep 26, 2022
675 views
What is the time & space complexity of this algorithm?Main(){ for(i=n; i>10; i=i^1/4) { for(j=201; j<n^3; j=j+400) ...
0 votes
0 votes
3 answers
3
Phlegmatic asked Jun 8, 2018
494 views
int main() { int i; for(i=1;i<=n;i++) f(i); } void f(int n) { int A[n]; int j; for(j=1;j<=n;j++) cout<<j; }What will be the time and space complexity of the following cod...