I am extremely new to Algorithms and time complexity and am going through a book. From what I know of Big-Oh function, it is not unique for any f(n),depending on constants c and n0. My first doubt is whether Master theorem gives the best case Big Oh function or not. My second doubt-might be silly- I got confused after after solving probs 1 and 2 while trying to proceed backwards and validate the answers.
Now my attempt is as follows-
1)cn2≥3T(n/2) + n2
⇒kn2≥T(n/2)
⇒k''(n/2)2≥T(n/2)
so it is consistent with O(n2).
Why does the same not go for prob 2,i.e why is it not O(n2) but O(n2logn)? I guess there is some maths behind it, and I want to know it (if I have sufficient background until now) .
Depending on your conditions, Masters theorem gives either the worst-case time complexity Big-O
or a tight bound Big-Theta
Now the actual proof of Master's theorem involves drawing the recurrence tree and some approximations using the geometric series progression. Here's a link to a pdf containing the process.