#Time Complexity for PseudoCode

1 messages · Page 1 of 1 (latest)

sturdy otter
#

Hi, I am reviewing for my data structures exam. How is this code constant time complexity?

austere palmBOT
#

<@&987246399047479336> please have a look, thanks.

#

Here is an AI assisted attempt to answer your question 🤖. Maybe it helps! In any case, a human is on the way 👍. To continue talking to the AI, you can use </chatgpt:1108714622413963314>.

#
TJ-Bot
Hi, I am reviewing for my data structures exam. How is this code constant time complexity?

Hey there! In order for code to have constant time complexity, it means that the runtime of the code does not depend on the size of the input.

In pseudo code, if you have a snippet like this:

function constantTimeExample(int[] array) {
    return array[0];
}

This function is considered to have constant time complexity because it only performs a single operation (returning the first element of the array) regardless of how large the input array is. The runtime will always be the same because it only ever accesses one element.

So, in your case, if your pseudo code performs a simple operation or access that doesn't change based on input size, then it can be considered to have constant time complexity.

However, it's important to note that in real-world scenarios, achieving true constant time complexity can be rare and often depends on factors such as hardware limitations. It's more common to see algorithms with logarithmic, linear, or quadratic time complexities in practice.

Hope this helps with your exam preparation! Let me know if you have any other questions.

- AI generated response
sturdy otter
#

prof says its O(n) but i think it is O(n^2) because its a nested loop. In the while loop, i goes from 0 to n-1, which makes n iterations. Inside the for loop, j goes from 0 to n-1, which makes n iterations as well. $$f(n) = c_1 + c_2 \cdot n \cdot c_3 \cdot n$$

#

aye no latex bot?

austere palmBOT
gray adder
#

ah this too

austere palmBOT
gray adder
#

anyway

#

to answer your question

sturdy otter
#

i typed the latex wrong

gray adder
#

look at the inner loop

#

"i" is incremented in the inner loop

#

so the inner loop complexity isn't independent from the outer loop

#

so it's not a multiplication of complexity

sturdy otter
#

are u saying that

#

this is in the for loop

gray adder
#

no

sturdy otter
#

the highlighted part

gray adder
#

line above

#

A[i++]

sturdy otter
#

ohhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh

gray adder
#

it's also a bit confusing that you using i<-i+1 at one place and i++ at another

#

please use one syntax

sturdy otter
#

my prof came up w that

#

LOL

#

so while loop only happens once

#

got it ty

gray adder
#

👍

sturdy otter