• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Junilu Lacar
  • Martin Vashko
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Scott Selikoff
  • salvin francis
  • Piet Souris

Algorithm Analysis

 
Ranch Hand
Posts: 347
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I got this question wrong on my test and I want to know why.
quiz.jpg
[Thumbnail for quiz.jpg]
 
Marshal
Posts: 7323
497
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So, you have a task to move 3 numbers to the back of an array.

Let's forget that for a moment.

Let's assume you need to take very first number and move it to the end of an array. What the time complexity would be? O(n). Why? That's because you'd need (going to say in simpler words, but not quite exactly what's happening) to take very first value and going step by step starting from the start position to a finish line. Meaning you'd need to go all the distance (array's length) once.

And so think of it you have done it in 5 seconds. So you ran through the distance of n in 5 seconds.

Now, the description says how the algorithm is implemented, "that you take one value at a time...".

So having said that, after you moved 1 element to an end of an array, you need to do the same now with the other first element (it was second in initial setup) - so it takes yet again 5 seconds.

Finally you need to take another first element and move it to the end - yet again 5 seconds.

So you moved 3 elements. m = 3, and n = 5s.

so O(m*n) = 15 s, makes sense, right?


It would be O(n) if you could take all 3 elements at once (check once again in instructions what is said about the used algorithm) and carry them over to the end of an array.
 
Liutauras Vilda
Marshal
Posts: 7323
497
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I just probably used N and M interchanged, so really according to an instructions M represents values in an array, while N represents a number of elements to move. I used them otherway round - but that doesn't change the answer, idea is the same.
 
Ana Smith
Ranch Hand
Posts: 347
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why is this statement true?
bigo.jpg
[Thumbnail for bigo.jpg]
 
Marshal
Posts: 66637
251
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why have you got log₁₀₀ in one place and log₂ in the other?
 
Saloon Keeper
Posts: 10875
235
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell, that's just the exam question and not a bad one at that. It illustrates that the base of the logarithm doesn't matter.

Ana, do you know what exactly O(log n) means?
 
Campbell Ritchie
Marshal
Posts: 66637
251
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's what I thought. But in that case surely the time complexity would be logN with the base omitted. After all, logs increase the same way irrespective of their base.
 
Stephan van Hulst
Saloon Keeper
Posts: 10875
235
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It doesn't matter. The argument to the O function may be any function. O(log₂ n) and O(log₁₀₀ n) return the same set. It's convention to write complexity classes using the simplest form, but it's not technically incorrect to pass in more information than needed.
 
Campbell Ritchie
Marshal
Posts: 66637
251
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sounds as though we are both thinking the same wway and expressing it differently. Agreed that you can have any base or no base for the log and it is still correct.
 
Ana Smith
Ranch Hand
Posts: 347
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:Campbell, that's just the exam question and not a bad one at that. It illustrates that the base of the logarithm doesn't matter.

Ana, do you know what exactly O(log n) means?


I know that it means log base 2 n.
 
Campbell Ritchie
Marshal
Posts: 66637
251
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Ana Smith wrote:

Stephan van Hulst wrote:. . . the base of the logarithm doesn't matter.

Ana, do you know what exactly O(log n) means?


I know that it means log base 2 n.

I think you have completely missed the whole point of this discussion.
 
Stephan van Hulst
Saloon Keeper
Posts: 10875
235
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Let me rephrase. What does O(n) stand for, what concept does it represent?
 
Liutauras Vilda
Marshal
Posts: 7323
497
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@OP

Log2(n) - let's multiply its base few times 2 x 2 x 2 = 8, and so if we had Log2(8) what the answer would be?

Log100(n) - let's multiply again its base few times 100 x 100 x 100 = 1000000, and so if we had Log100(1000000) what the answer would be?
 
Liutauras Vilda
Marshal
Posts: 7323
497
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Maybe reminding yourself some definition would help to derive to some conclusion.

"The runtime O(f(n)) means that with the growth of n the runtime of the program grows proportionally to fuction f(n)."

Now in a case of Log2(8) and Log100(1000000), we increased n significantly, but how the answer differed?

Answer questions in the post above and you'll know the answer.
 
Campbell Ritchie
Marshal
Posts: 66637
251
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also go back to your older thread; in the case of nlogn complexity, I had a little formula. If you go and change the two instances of log there to log₂ or log₁₀₀ or some other base, and see what the result comes to. You can simplify that formula a bit to match logn time complexity
 
Bartender
Posts: 3674
151
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And yet another clue:

remember the formula from school:  Log_a(b) = Log_c(b) / Log_c(a), so Log_a(b) and Log_c(b) differ by a constant factor. See the def of Big_O what that means for O(Log_a) and O(Log_c)
 
Marshal
Posts: 14530
242
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think in this case it might be helpful to give OP a more direct answer.

The statement in question is true because Big O is about the shape of the curve. That means you can ignore things like constants, e.g., the base of the log.

See this: https://stackoverflow.com/questions/20512642/big-o-confusion-log2n-vs-log3n/20512708#20512708
 
Is that a spider in your hair? Here, threaten it with this tiny ad:
Sauce Labs - World's Largest Continuous Testing Cloud for Websites and Mobile Apps
https://coderanch.com/t/722574/Sauce-Labs-World-Largest-Continuous
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!