mira pareksha wrote:
Answer:O(lg3n)
There are three kinds of actuaries: those who can count, and those who can't.
Piet Souris wrote:
2) agree with Stephan, O(n + log(n))
The 'j' loop is O(n), the 'k' loop is O(log(n))
mira pareksha wrote:Actually in the outer loop even though the condition is i++ but each time i is multiplied by three so I thought that the complexity might be log base 3
and the inner loop is always executed constant number of times then its O(1). So as a result we get O(lg 3 n) as a complexity for these algorithm. Am I thinking right??
I think it is correct, as these two are independent.Stephan van Hulst wrote:I think the one where you answered O(n) is wrong.
Yes, probably I was wrong here, have to agree with Stephan and Piet, this one will be O(n + log(n)) and it is exactly because these are independed. The last one actually very similar example from first glance, but is nested, so the last one is O(n).Liutauras Vilda wrote:
I think it is correct, as these two are independent.Stephan van Hulst wrote:I think the one where you answered O(n) is wrong.
mira pareksha wrote:Answer: Actually this one was hard but I think it's O(n^2)
Henry Wong wrote:
Piet Souris wrote:
2) agree with Stephan, O(n + log(n))
The 'j' loop is O(n), the 'k' loop is O(log(n))
For this example, I believe the OP is correct ... since ...
O(n + log(n)) == O(n)
Henry
There are three kinds of actuaries: those who can count, and those who can't.
Piet Souris wrote:However, in a course I did on algorithms I was given a similar question,
albeit that the second loop had an m, instead of an n.
I could prove that 0 < m <= n.
It was a multiple choice question, though, and among the options were:
1) O(n)
2) O(n + m)
So I chose 1), but it was incorrect. 2) was correct, since 'it characterized the problem better'.
Therefore, the correct answer depends on the mutiple choice options.
pie. tiny ad:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filleradvertising
