CODEWITHSUNDEEP
algorithmtime-complexity
Navid Koochooloo
Navid Koochooloo

Reputation: 277

time complexity and size of the input

I'm studying for an exam which is mostly about the time complexity. I've encountered a problem while solving these four questions.

1) if we prove that an algorithm has a time complexity of theta(n^2), is it possible that it takes him the time calculation of O(n) for ALL inputs?

2) if we prove that an algorithm has a time complexity of theta(n^2), is it possible that it takes him the time calculation of O(n) for SOME inputs?

3) if we prove that an algorithm has a time complexity of O(n^2), is it possible that it takes him the time calculation of O(n) for SOME inputs?

4) if we prove that an algorithm has a time complexity of O(n^2), is it possible that it takes him the time calculation of O(n) for ALL inputs?

can anyone tell me how to answer such questions. I'm mostly confused when they ask for "all" or "some" inputs. thanks

Upvotes: 3

Views: 2002

Answers (2)

user1300630
user1300630

Reputation:

A "barfoot" explanation:

Big O notation is for setting an upper bound. By definition, there is always an index(or an input-length) from wich the notation is correct. So below this index, anything can happen.

For example sorting an array(O(n^2)) with one element takes less time, than writing the elements to the output(O(n)). ( we don't sort, we know it is in the right order, so it takes 0 time ).

So the answers:

  • 1: No
  • 2: Yes
  • 3: Yes
  • 4: Yes

You can find a detailed understandable description at WIKI

And HERE You can find a simpler explanation.

Upvotes: 1

Tony Morris
Tony Morris

Reputation: 445

gkovacs90 answer provides a good link : WIKI

  • T(n) = O(n3), means T(n) grows asymptotically no faster than n3. A constant k>0 exists and for all n>N , T(n) < k*n3
  • T(n) = Θ(n3), means T(n) grows asymptotically as fast as n3. Two constants k1, k2 >0 exist and for all n>N , k1*n3 < T(n) < k2*n3

so if T(n) = n3 + 2*n + 3

Then T(n) = Θ(n3) is more appropriate than T(n) = O(n3) since we have more information about the way T(n) behaves asymptotically.

T(n) = Θ(n3) means that for n>N the curve of T(n) will "approach" and "stay close" to the curve of k*n3, with k>0. T(n) = O(n3) means that for n>N the curve of T(n) will always be under to the curve of k*n3, with k>0.

  • 1:No
  • 2:Yes, as gkovacs90 says, for small values of n you can have O(n) time calculation but I would say No for big enough inputs. The notations Theta and Big-O only mean something asymptotically
  • 3:Yes
  • 4:Yes

Example for number 4 (dumm but still true) : for an Array A : Int[] compute the sum of the values. Your algorithm certainly will be :

Given A an Int Array

sum=0 
for int a in A
    sum = sum + a
end for
return sum

If n is the length of the array A : The time complexity is T(n) = n. So T(n) = O(n2) since T(n) will not grow faster than n2. And still we have for all array a time calculation of O(n).

If you find such a result for a time (or memory) complexity. Then you can (and certainly you must) refine the Big-O / Theta of your function (here obviously we have : Θ(n))

Some last points :

  • T(n)=Θ(g(n)) implies T(n)=O(g(n)).
  • In computational complexity theory, the complexity is sometimes computed for best, worst and average cases.

Upvotes: 2

Related Questions