can any1 solve this .....Given a sorted list of infinite size in which first n elements (n is unknown) are finite integers and rest are infinity, write an efficient function that finds a given number in O(ln n ) time complexity.
jaanu.cheruvu
0
Newbie Poster
Recommended Answers
Jump to PostSo what's with all the smoke about "infinity" then?
You have n sorted integers.
Jump to PostEvidently it's impossible in terms of element access counter because no direct access to list elements so you need ~n/2 accesses to fetch a given number from a list -
O(n)
time complexity.If n denotes a number of comparisons - it's the other story. It's so simple ;)...
…
All 8 Replies
Salem
5,138
Posting Sage
jaanu.cheruvu
0
Newbie Poster
ArkM
1,090
Postaholic
jaanu.cheruvu
0
Newbie Poster
Rashakil Fol
978
Super Senior Demiposter
Team Colleague
jaanu.cheruvu
0
Newbie Poster
nucleon
114
Posting Pro in Training
jaanu.cheruvu
0
Newbie Poster
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.