Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

complexity of algorithm [closed]

I would have quite general question. Have you ever had to really compute(e.g on the paper) complexity of an algorithm except at school as a programmer? And if.. can you give me an example please.

thank you :)

like image 619
michal Avatar asked Feb 03 '09 18:02

michal


People also ask

How do you find the complexity of an algorithm?

If your algorithm runs in a time proportional to the logarithm of the input data size, that is log ⁡ ( n ) \log(n) log(n), then you have O ( log ⁡ ( n ) ) \mathcal{O}(\log(n)) O(log(n)) complexity. This type of complexity is usually present in algorithms that somehow divide the input size.

What is O n2 complexity?

O(n2) represents a function whose complexity is directly proportional to the square of the input size. Adding more nested iterations through the input will increase the complexity which could then represent O(n3) with 3 total iterations and O(n4) with 4 total iterations.

Which is the algorithm complexity?

Algorithmic complexity is concerned about how fast or slow particular algorithm performs. We define complexity as a numerical function T(n) - time versus the input size n. We want to define time taken by an algorithm without depending on the implementation details.

Which algorithm has highest time complexity?

Linear time is the best possible time complexity in situations where the algorithm has to sequentially read its entire input.


1 Answers

If you're writing a piece of software and you can think of multiple ways to implement it, often one of the deciding factors (in addition to conceptual complexity and time to implement) is going to be the algorithmic complexity. Thus, when your boss wants justification for your decision, figuring out the complexity of each is necessary. While some may consider this a form of premature optimization, I think the consensus is that choosing a design appropriate for your problem is just good software engineering.

like image 53
rmeador Avatar answered Sep 21 '22 17:09

rmeador