Skip to content
This repository was archived by the owner on Mar 3, 2026. It is now read-only.

Latest commit

 

History

History
28 lines (26 loc) · 1.17 KB

ProblemsComplexity.md

File metadata and controls

28 lines (26 loc) · 1.17 KB

Problems Complexity

Note

Every problem can have a lower or higher bound.

The core is that a problem can be Theta n
Becouse there is a solution that works on Theta n
But every other Solution/Algorithm that is slower still is a solution

If a solution is faster then a lowebound means:

  • 1 The soulution you found has some kind of errors
  • 2 You have just found a new lowerbound

How to define a lowerbound? Spoiler is kinda hard

  • Mostly is already asked in the problem
The sum of all numebers till N
Has to be at least Omega N

Remember the difference beetween problems that use confronts and the ones who doesn't

There are NP-Complet problems that can't be solved in polinomial time.

Decisional tree (search for comparison)

Is a tree where every internal node is a confronts and leaves are the output. The lenght of a tree is Log(n)

For this reason a sorting by comparison is at least $n*\log(n)$.

Tip

When we write log(n) we ignore the base of the log since may be use tree not binary but tertiary or more.

-Suggested to have a look on teacher pdf for a complete explanation and examples.