Algorithm Complexity how do I tell

Thread starter zeion
Start date Mar 13, 2012
Tags

Algorithm Complexity

AI Thread Summary

The discussion centers on analyzing the complexity of the recurrence relation T(n) = log_{3/2} n lg(n) + (log_{3/2}(n) (log_{3/2}(n) - 1 ) /2) lg(2/3). The focus is on determining the order of complexity based on the dominant term as n increases. The dominant term is crucial for understanding the behavior of the algorithm's performance for large inputs, and it is emphasized that identifying this term will provide insight into the overall complexity classification.

Mar 13, 2012

zeion

Hi,

If the algorithm recurrence can be shown to belong to something complicated say like

T(n) = log_{3/2} n lg(n) + (log_{3/2}(n) (log_{3/2}(n) - 1 ) /2) lg(2/3)

What order of complexity can I expect it to be in?

Technology news on Phys.org

Mar 17, 2012

Max.Planck

In the order of the dominant term. So the term that is going to matter most when n is large.

Thread 'Learning Assembly and computer architecture for x86'

Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...

View full post »

Thread 'Microsoft Technical Interview question'

I had a Microsoft Technical interview this past Friday, the question I was asked was this : How do you find the middle value for a dataset that is too big to fit in RAM? I was not able to figure this out during the interview, but I have been look in this all weekend and I read something online that said it can be done at O(N) using something called the counting sort histogram algorithm ( I did not learn that in my advanced data structures and algorithms class). I have watched some youtube...

View full post »