CODEWITHSUNDEEP
algorithmcomplexity-theorybig-o
user1013237
user1013237

Reputation: 33

How can i compute complexity

I have found out that my algorithm will always do n!*4^n steps . I'd like to know wheter its complexity will be O(n!*4^n) or will it be something else? Thanks.

Upvotes: 3

Views: 253

Answers (3)

Saeed Amiri
Saeed Amiri

Reputation: 22555

It's Θ(n!⋅4ⁿ) and because Θ is lower bound for O it's also O(n!⋅4ⁿ) Also It's Ω(n!⋅4ⁿ).

Just important thing is what you doing in your steps? If each step is O(1) this notations hold, but in other cases, it's depend to your steps, I suggest show us your function, to see what's the steps.

And why you can't say it's O(n!)? because you can't find constant c such that:

n!⋅4ⁿ ≤ c⋅n!, for n > n0

because for any constant c when 4ⁿ > c (for example when n ≥ c) above inequality is wrong.

Upvotes: 3

Aurelio De Rosa
Aurelio De Rosa

Reputation: 22152

If you are sure that your algorithm will do always n!⋅4ⁿ steps, it's a O(n!⋅4ⁿ) as well as it's a Θ(n!⋅4ⁿ) as well as it's a Ω(n!⋅4ⁿ).

Upvotes: 3

Dennis
Dennis

Reputation: 14477

If it does exactly n!*4^n steps, there's no real need for big oh notation.

And yes, that means it has O(n!*4^n) complexity.

Upvotes: 1

Related Questions