This week's book giveaway is in the Kotlin forum.We're giving away four copies of Kotlin for Android App Development and have Peter Sommerhoff on-line!See this thread for details.
Win a copy of Kotlin for Android App Development this week in the Kotlin forum!
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
• Devaka Cooray
• Jeanne Boyarsky
• Bear Bibeault
Sheriffs:
• Junilu Lacar
• Paul Clapham
• Knute Snortum
Saloon Keepers:
• Ron McLeod
• Tim Moores
• Stephan van Hulst
• salvin francis
• Carey Brown
Bartenders:
• Tim Holloway
• Frits Walraven
• Ganesh Patekar

# Time complexity and binary search trees

Greenhorn
Posts: 3
Hi everyone!

I've been recently asked by one of my friends to help him out with these two following questions.

1.Find the time complexity of this two piece of code and write which one is bigger?

2.An algorithm that takes the roots of two same Binary Search Trees. if the roots are same return TRUE and if not return FALSE.
(corresponding nodes have the same values.)

lowercase baba
Posts: 12706
50
So, what do you think?  People here won't just do this work for you. We're happy to discuss your thoughts, but you have to do some of the work first.

So tell us what you think the complexity of each is, and why.

miller anderson
Greenhorn
Posts: 3
for the first case,
line 1, we can write a sigma from i=2 to root of n
but for the 2nd line Im not sure if still i'm allowed to use SIGMA cause (j) is LESS than or equal to i, and also the value of j depends on (I) from line 1. so that's why I think I should not use sigma for the 2nd line.

for the second code:
line 2nd and 3rd both execute 1 time so I think, O(1), right?

miller anderson
Greenhorn
Posts: 3
And for the second question, I really dont know where to start from, that is why I need some help to get started.
thanks again and again.

Master Rancher
Posts: 3080
108
hi millar,

In the first case, when n = 2, we get that i = 2, and j goes from 2 to 2. That is 1 time. If n = 3, we get that j is executed 1 time (i = 2), and then 2 times (when i = 3). So, when n = 3, we have 1 + 2 = 3 times. When n = 4, check that we get 1 + 2 + 3 = 6 times.
So, when n = N, we are bound to get 1 + 2 + ... + (N - 1) times. This series has a well known sum. So, can you tell what time complexity it has?

Try to deduce something similar for the second case.

Marshal
Posts: 62881
203
Welcome to the Ranch

What do you know about complexities? How much have you been taught?

Piet Souris
Master Rancher
Posts: 3080
108
Oops... I completely screwed up, missed the 'i = i * i' and 'j = j * j'. Sorry for that!

Well, that change makes it somewhat harder. What I do in these cases is calculating both methods for several different input values, list the output and try to see some connection between the input and output. I used, as input, the values 2, 4, 8, 16, ... up to 2^100 (be careful, use BigIntegers). You see first that, after a certain input value, that the second method is calculated more than the first method. For instance, when n = 2 ^51, the first method is calculated 21 times, the second 51 times. The  second method has O(2log(n)) = O(ln(n)), the first is more complicated, you get that 2 ^(2 ^n) gives a count of 1 + 2 + ... + (n + 1), with a floor function for intermediate values.

Piet Souris
Master Rancher
Posts: 3080
108
Oh no, not again!

But can you elaborate a little? I used this code:

 All of the world's problems can be solved in a garden - Geoff Lawton. Tiny ad: RavenDB is an Open Source NoSQL Database thatâ€™s fully transactional (ACID) across your database https://coderanch.com/t/704633/RavenDB-Open-Source-NoSQL-Database