Note
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
- 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
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
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.