Big o Time complexity

Question

What will be upper bound for following function?

T(n)=n^2 - n^4

a) O(n^2)

b) O(n^3)

c) O(n^4)

d) None of these

I want to understand how the function looks like if it has recurrance of this form?What is meaning of subtraction here if i talk in terms of programming

Comments

The recurrence relation is supposed to provide no of comparisons or steps taken to solve a problem. Now the function you are providing is clearly negative. How can no or comparisons/steps/executions be negative??

---

There was one similar question like https://gateoverflow.in/92780/algorithms-time-complexity

---

@akashsheoran is right :)

Answer 1

This is pretty interesting  Question :)

Q]  What will be upper bound for following function?

The upper bond of the folowing function will be $O(n^{4})$ I need not explain because you have already seen the reference (https://gateoverflow.in/92780/algorithms-time-complexity) We take modulus of the function and calculate the complexity .

Q] I want to understand how the function looks like if it has recurrance of this form?What is meaning of subtraction here if i talk in terms of programming

Recurrence of the form $T(n)=n^{2} - n^{4} $ has got no meaning in real programming . Perhaps these -ve terms in recurrence relations are introduced just to make confusions . In any standard algorithm or Questions all terms in the recurrence relation denoting a code will always contains positive terms only. There is NO MEANING if subtraction is used in recurrence in terms of programming point of view

Comments

Thank you for explanation @pc.

Please clear follwoing points:-

1. Why we take mod for fxn?If i dont take mod that what would be the scenario?

2. In the reference post also the value of f(n) as -ve,so it means no comparisions are done?In my question also f(n) will be -ve.How can we select n^4 as upper bound by taking mod?

Say I have a piece of code like:-

for(i=1 to n)
{
    if(i%2==0)
    for(j=1 to n)
    {
        //Do some thing
    }
    //constant operation
}
Now I can say complexity is :- (n-n/2)*n +(n-n/2)*1 => means half iterations took n time and half time constant time.
This can be written as  (n^2-n^2/2) +n-n/2.There is -ve sign but we dont want to take mod.
If we simplify further we will get in highest degree power if n^2.
Now if i talk about actual question above in this post ,it will always be -ve means nothing is done ,so why is it not constant?0(1)?Are we saying that fxn is growing on -ve side and by taking mod we are getting same behaviour on +ve side of graph
 

I hope my question makes sense.Please help

---

@rahul_sharma_5 ,

 Its because in practice there is no -ve ly growing recurrecurrance relations for any piece of code .  These stuffs are introduced by  coaching institutes to create confusions . You check for any standard references or university questions . Then we can discuss . I havn't seen any negative term while drafting recurrence relations from code :( AFAIK There is no practical meaning also.

That refrence questions has also got no meaning in real programming .

Rate of Growth of Function will depends on higer order functions. That is why it is $O(n^{4})$

In the code snippet you have given i could NOT  understand how you are getting
$(n-\frac{n}{2})*n +(n-\frac{n}{2})*1$

In the above code

$\frac{n}{2}*n +\frac{n}{2}*1$
Outer Loops runs for n times and for half of the iterations (ie when the if conditions becomes true  ) the inner loop also executes n times hence total time wil be $O(n^{2})$

This is all what I knew.
ping @arjun sir. He can help you much better . Espicially in Algorithms  :)

---

@pc. They are asking for the upper bound on the value of the function.

Since, the values are negative after a certain point, O(1) will suffice. So, this question is wrong.