Calculate Time complexity of this algorithm...

[Qubit]

 

I'm concerned with 1c. I developed pseducode for this algorithm and computed it in O(n) time and space complexity. The TA otherwise told me I am wrong and the complexities are O(n^2) . All in all because they marked it wrong, I received an 89 in course rather than a 90.  My school only gives As and Bs... So instead of a 4.0 I got  3.0 for the class.   So tell me am I wrong.?

 

 

 

Edited December 19, 2016 by Qubit

[Rxd]

Bro osbot aint a homework site.

 

[Chicken Wing]

Well, what was the algorithm?

[Santonio]

Lol to hard for me

[Qubit]

Bro osbot aint a homework site.

 

 I find most interest n the development side of osbot. I quite often share problems I come across, if you don't like it, go eat a dick.

 

Sincerely Yours,

Qubit

Well, what was the algorithm?

https://gist.github.com/jaavant/5ae6f6296ce720bd43591f678fa8762e

[Rxd]

 I find most interest n the development side of osbot. I quite often share problems I come across, if you don't like it, go eat a dick.

 

Sincerely Yours,

Qubit

https://gist.github.com/jaavant/5ae6f6296ce720bd43591f678fa8762e

Sharing problems you come across?

Like crying over a 89 lmfao thinking it's going to change your grade.

[Explv]

I'm flaming? Seem's like you're the uneducated fuck here retard.

I'm 17 lmfao calm your tits. What you expect me to know bout this shit? fucking nerd.

Edit: I was nice to your bitch ass than you got pissed over some kiddy shit

Not too sure why you keep commenting on these threads if you have no knowledge of the subject area and cannot answer OP's question. You did this on the last thread he posted too.

Although this is an osrs bot website, this is the "Programming" section, and OP's question is perfectly valid, and there are users here who can answer his question.

Perhaps in the future you should just not reply unless you have an answer.

Edited December 20, 2016 by Explv

[Explv]

 

I'm concerned with 1c. I developed pseducode for this algorithm and computed it in O(n) time and space complexity. The TA otherwise told me I am wrong and the complexities are O(n^2) . All in all because they marked it wrong, I received an 89 in course rather than a 90.  My school only gives As and Bs... So instead of a 4.0 I got  3.0 for the class.   So tell me am I wrong.?

 

 

I have skimmed your code and to me it does look like time and space complexities would be O(n).

 

Time complexity:

 

You visit each node exactly once (there are no repeated visits because you store the shortest path from that node in a HashTable). Therefore the complexity is O(n). 

 

Space complexity:

 

You store the sum of the shortest path from each node in a HashTable therefore the space complexity is O(n)

 

I have no idea where they got O(n^2) from

 

That is of course assuming that your Java implementation is identical to your pseudo code. I could only really tell you if your TA was wrong if you posted the actual pseudo code you wrote in the exam.

Edited December 20, 2016 by Explv

[Botre]

The Hashtable class is obsolete.
You're using a Hashtable without overriding the key class' hashCode() & equals() methods.
You hardcoded your base case (if 4 == r).
3 ints and 2 object references per node. Memory.
Redundant calls to table.contains(key) & table.get(key).

The way you construct your TreeNode class is the opposite of elegant and intuitive.

 

Your algo might not be O(n^2) but if your pseudo code looked anything like this Java implementation, I can't blame the TA for not giving you a perfect grade.

 

[Qubit]

The Hashtable class is obsolete.

You're using a Hashtable without overriding the key class' hashCode() & equals() methods.

You hardcoded your base case (if 4 == r).

3 ints and 2 object references per node. Memory.

Redundant calls to table.contains(key) & table.get(key).

The way you construct your TreeNode class is the opposite of elegant and intuitive.

 

Your algo might not be O(n^2) but if your pseudo code looked anything like this Java implementation, I can't blame the TA for not giving you a perfect grade.

 

I changed the code recently to increment rather than decrement, The statement was if r == 1...  It just looks better and ill probably change it.  Probably would look alot cleaner in C, but aint nobody got time to be doing all this extra work to prove that they are wrong. The assignment was not to code anything. I just threw this code together just to prove that it could be done in O(n) space and time complexity :P

Edited December 20, 2016 by Qubit

[Decode]

No more spamming this thread please. Next person to post an irrelevant comment will be punished. 

[Jake]

No more spamming this thread please. Next person to post an irrelevant comment will be punished. 

 

But its in spam ?

 

 

[Decode]

But its in spam ?

 

 

 

 

Im a retard

 

Didn't notice that this was in the spam/off topic section >.> 

 

Apologies lads, feel free to spam  

[Jordan]

Im a retard

 

Didn't notice that this was in the spam/off topic section >.> 

 

Apologies lads, feel free to spam

ty

[jackshow]

Im a retard

 

Didn't notice that this was in the spam/off topic section >.> 

 

Apologies lads, feel free to spam

Edited December 30, 2016 by jackshow