CODEWITHSUNDEEP
time-complexity
user349026
user349026

Reputation:

Are there any common techniques used for calculating Algorithm Complexity?

I wonder if there are any common or best practice techniques out there if one needs to find the complexity of algorithms?

Upvotes: 1

Views: 382

Answers (2)

Neil
Neil

Reputation: 5782

O(1) means you perform a series of instructions a constant number of times (which simply put means you don't use any loops).

O(n) means you have one loop which performs O(1) operations inside (for example I search through a list for a specific value).

O(log n) is searching through a list utilizing an intelligent indexing system such as a binary tree or hash map. With every pass, you're essentially eliminating half the possibilities (unlike O(n) which eliminates them one at a time).

O(n^2) means you have an inner and outer loop for performing cross checks (if I wanted to cycle through all items in an grid, I'd start by cycling through all rows and then through each cell of each row for instance). You could generalize this as O(n^m) where m represents the maximum loop depth in your program which cycles for n times.

O(2^n) means that you're cycling through every possible combination of a set. If I have items {A, B}, then cycling through every possible combination would result in {{}, {A}, {B}, {AB}}.

O(n!) is exhausting every possible scenario. Trying to crack a password through brute force is an example of O(n!). You can't get worse than this, and algorithms which are O(n!) exist because there are no other alternatives (P and NP complete for example).

This is a fairly quick summary, but that's the gist of it. Technically loops which cycle a constant number of times are O(1) unless it contains an inner loop. What's important is that you're not looping an unknown number of times.

Upvotes: 6

Oded
Oded

Reputation: 498992

Big O is standard.

Although developed as a part of pure mathematics, this notation is now frequently also used in the analysis of algorithms to describe an algorithm's usage of computational resources: the worst case or average case running time or memory usage of an algorithm is often expressed as a function of the length of its input using big O notation.

Upvotes: 4

Related Questions