CODEWITHSUNDEEP
algorithmtime-complexity
vinaych
vinaych

Reputation: 79

Algorithm Complexity for runtime involving 2 seperate variables

I have an algorithm that runs in ab time where a and b are both separate inputs.

Is my algorithm polynomial time complexity algorithm still or is it nn? I think nn is non polynomial but I am still not sure about that as well.

I see factorial of n algorithm still evaluates to nn complexity so nn must be non polynomial too. Please help and clarify my doubts.

Upvotes: 0

Views: 44

Answers (1)

Ulrich Schwarz
Ulrich Schwarz

Reputation: 7727

If b is part of the input, your running time is not polynomial. (Try giving the degree of the polynomial that bounds it!)

In some areas, special subproblems are studied (graphs with bounded degree come to mind, or packing with a constant number of sizes) so you cay say that yes, for a fixed b your algorithm is polynomial in a.

Upvotes: 1

Related Questions