• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Tim Cooke
  • Jeanne Boyarsky
  • Liutauras Vilda
Sheriffs:
  • Frank Carver
  • Henry Wong
  • Ron McLeod
Saloon Keepers:
  • Tim Moores
  • Frits Walraven
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Himai Minh

Few Big-oh questions

 
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi guys
First of all, thank you for this amazing forum. Indeed I'm learning a lot from it
In my preparations for the exam I tried to solve the following Big-Oh questions, so can you check them for me



Answer:O(lg3n)




Answer: O(n)



Answer: O(mn)



Answer: Actually this one was hard but I think it's O(n^2)
 
author
Posts: 23928
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

mira pareksha wrote:


Answer:O(lg3n)



Can you explain to us how you reached this answer? And also, can you explain how the base of the log is even relevant (assuming that is what the 3 is).

Henry
 
mira pareksha
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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??
 
mira pareksha
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
can you help me by checking my solutions posted above
I'm still somehow lost
 
Saloon Keeper
Posts: 14268
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think the one where you answered O(n) is wrong.
 
Bartender
Posts: 5061
188
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
1) and 3): oke

2) agree with Stephan, O(n + log(n))
The 'j' loop is O(n), the 'k' loop is O(log(n))

4) O(n)
The í' loop is done n times, and for each i the 'j' loop is done 8 times.
All in all O(8n) = O(n)

One way to get an impression whether the outcome is n or log(n) alike,
is to add a global counter, let it run for n = 10, 100, 1000, ..., 100.000.000
and with a bit of luck you get some reckognizable outcome. I would not do
this for say O(n^>=2) functions or worse)

For instance in the last one, you would get:

 
Henry Wong
author
Posts: 23928
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Henry Wong
author
Posts: 23928
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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??



Since the log N (base X) is equal to log N (base Y) divided by log X (base Y), it doesn't matter what base is used. The base of the log in the complexity is not relevant.

Henry
 
Marshal
Posts: 8395
601
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Stephan van Hulst wrote:I think the one where you answered O(n) is wrong.

I think it is correct, as these two are independent.
 
Liutauras Vilda
Marshal
Posts: 8395
601
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Last one I think is wrong. As inner loop always runs constant time, 8 iterations. Outer n times.
 
Liutauras Vilda
Marshal
Posts: 8395
601
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:

Stephan van Hulst wrote:I think the one where you answered O(n) is wrong.

I think it is correct, as these two are independent.

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
Marshal
Posts: 8395
601
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

mira pareksha wrote:Answer: Actually this one was hard but I think it's O(n^2)


that would look similar to as both need to run n, inner and outer.
 
Stephan van Hulst
Saloon Keeper
Posts: 14268
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I was incorrect. O(n) is correct. It's because of the indentation, I though the second loop was nested within the first loop, then it would have been O(n log n). Since the loops are independent, the one with the higher complexity counts, which is O(n).
 
Piet Souris
Bartender
Posts: 5061
188
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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


Actually, I agree, since n + log(n) < 2n, for n >= 1.

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.
 
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.



That depends on whether you consider "correct" to mean "correct" or "will be marked as correct" . I'd say O(n + m) is misleading if one can be bounded by the other, so doesn't characterise it better.

An example where you get a genuine O(n + m) is a simple graph search (where n is the number of vertices and m is the number of edges). In this case m = O(n^2), but m can also be small (in a sparse, unconnected graph), so O(m) would be inaccurate.

 
pie. tiny ad:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic