This week's giveaway is in the Cloud/Virtualization forum.We're giving away four copies of Production-Ready Serverless (Operational Best Practices) and have Yan Cui on-line!See this thread for details.
Win a copy of Production-Ready Serverless (Operational Best Practices) this week in the Cloud/Virtualization 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
• Bear Bibeault
• Jeanne Boyarsky
• paul wheaton
Sheriffs:
• Junilu Lacar
• Paul Clapham
• Knute Snortum
Saloon Keepers:
• Stephan van Hulst
• Ron McLeod
• Tim Moores
• salvin francis
• Carey Brown
Bartenders:
• Tim Holloway
• Frits Walraven
• Vijitha Kumara

# 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: 12734
51
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
Thank you buddy for replying.
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.

Rancher
Posts: 3111
110
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: 63781
209
Welcome to the Ranch

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

Piet Souris
Rancher
Posts: 3111
110
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
Rancher
Posts: 3111
110
Oh no, not again!

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

 The two armies met. But instead of battle, they decided to eat some pie and contemplate this tiny ad: global solutions you can do in your home or backyard https://coderanch.com/t/708587/global-solutions-home-backyard