dealth
asked on
Big O Calculations for log2n
I have a question put forward by my professor just for thinking and since I'm not familiar with C++ I'm having a hard time thinking the answer???
the question is:
A function using an algorithm with a worst case running time of O (log2 n). n = 30 and n = 1000
I have written the following function and was wondering if it was correct???
function6(int n, int n1)
{
fnumber_one = (log(n) * log (n)) / log(2);
fnumber_two = (log(n1) * log(n1)) / log(2);
return fnumber_one, fnumber_two;
}
Thanks in advance.
the question is:
A function using an algorithm with a worst case running time of O (log2 n). n = 30 and n = 1000
I have written the following function and was wondering if it was correct???
function6(int n, int n1)
{
fnumber_one = (log(n) * log (n)) / log(2);
fnumber_two = (log(n1) * log(n1)) / log(2);
return fnumber_one, fnumber_two;
}
Thanks in advance.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
an algorithm in O(n) means that the order of magnitude of ***some way of counting*** operations is n
for instance, a pure linear algorithm for computing a*n in n operations of + in a loop (ok? :D ) is in O(n) if the counted operations are additions.
In memory accesses or affectations, it's different.
***Usually***, this way of measuring the COMPLEXITY of an algorithm does express itself in clock cycles, that is, people "ponder"(weight) more multiplications and division than addition and substractions, themselves weighting more than tests, affectations (memory writes) and memory read (accesses).
A ***nice*** complexity measured is in all of this and really expresses the complexity of the lgorithm in real life, ie it will give a neat view on the SPEED of the process associated with the algorithm.
"complexité en temps"
The complexity could ALSO be defined in "space" (memory consumption) ("complexité en espace")
algorithm : static defining the suit of operations to perform
process : dynamic implementing the above
So, for you, your professor asks you to exhibit an algorithm having an order of complexity (in WHAT?) of O(log2(n))
Clearly, this could rely to some binary tree function or dichomotic search.
PS : I hope you did not say Log2.n for Log10²(n) or Ln²(n)
Having done some research in existing algorithms in the two areas mentioned above, this is ***an*** answer to your question :
the worst-case complexity order in number of comparisons (tests) to find the 2nd element amongst n elements using the algorithm or the tournament is Max(n) = n + ceiling(log2(n))-2 because the algorithm requires at worst ceiling(log2(n))-1 comparisons on a binary tree of a tournament with n players, which is of height h(n)=ceiling(log2(n))
for instance, a pure linear algorithm for computing a*n in n operations of + in a loop (ok? :D ) is in O(n) if the counted operations are additions.
In memory accesses or affectations, it's different.
***Usually***, this way of measuring the COMPLEXITY of an algorithm does express itself in clock cycles, that is, people "ponder"(weight) more multiplications and division than addition and substractions, themselves weighting more than tests, affectations (memory writes) and memory read (accesses).
A ***nice*** complexity measured is in all of this and really expresses the complexity of the lgorithm in real life, ie it will give a neat view on the SPEED of the process associated with the algorithm.
"complexité en temps"
The complexity could ALSO be defined in "space" (memory consumption) ("complexité en espace")
algorithm : static defining the suit of operations to perform
process : dynamic implementing the above
So, for you, your professor asks you to exhibit an algorithm having an order of complexity (in WHAT?) of O(log2(n))
Clearly, this could rely to some binary tree function or dichomotic search.
PS : I hope you did not say Log2.n for Log10²(n) or Ln²(n)
Having done some research in existing algorithms in the two areas mentioned above, this is ***an*** answer to your question :
the worst-case complexity order in number of comparisons (tests) to find the 2nd element amongst n elements using the algorithm or the tournament is Max(n) = n + ceiling(log2(n))-2 because the algorithm requires at worst ceiling(log2(n))-1 comparisons on a binary tree of a tournament with n players, which is of height h(n)=ceiling(log2(n))
ASKER
thanks a lot, will implement the above.
You accepted a wrong answer, though 8-))
"big O notation measures function effeciency in terms of loops" : false and incomplete
1) it's complexity, not efficiency
2) not always loops
3) there's "small o" notation too
4) this is maths
"big O notation measures function effeciency in terms of loops" : false and incomplete
1) it's complexity, not efficiency
2) not always loops
3) there's "small o" notation too
4) this is maths
Big O infact measures efficieny not complexity... I know that for sure. If you want to call it complexity in the fact that it takes more time to execute then you can call it complexity, but its effeciency, I got exactly what I told him out of a data structures book by gilberg and forouzan. In addition I also got an A on the Big O notation. f(n) = effecieny, O(n) is a short notaion for f(n), you drop the coeefficents and use the fastest growing term. hence it measures effeciency.
8-))))))))))))))))))))))))
ASKER
n = 30 and n = 1000
not O = 30 and O = 1000