1 Replies - 233 Views - Last Post: 07 February 2019 - 01:44 AM Rate Topic: -----

#1 miller72   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 06-February 19

BSTs, time complexity

Posted 06 February 2019 - 03:11 PM

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?

for( int i=2 ; i<= n; i=i*i )
for( int j=2 ; j <= i; j=j*j )
print(j);


while ( n>1 ){
print(n);
n=n/2;
}



what I think so far for 1st question:
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?




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.)

for this question I have no clue and dont know where to start from, and 've searched a lot so far, but not successful yet...

Is This A Good Question/Topic? 0
  • +

Replies To: BSTs, time complexity

#2 andrewsw   User is online

  • Stealth IT
  • member icon

Reputation: 6737
  • View blog
  • Posts: 27,746
  • Joined: 12-December 12

Re: BSTs, time complexity

Posted 07 February 2019 - 01:44 AM

What assistance is your friend offering?

For reference, also posted at stackexchange and sitepoint
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1