1

I'm new to calculating complexity so this is confusing me. If my code get an unknown length (n) array of integers, suppose that the array (arr) is sorted already and I want for loop like this:

for (int k=0; k<arr[n-1]; k++);

Does this code complexity is O(1) or O(n)?

I'm used to calculate complexity depend on itaration as function of length but here it depend on the data inside the array.

Improve this question
5
  • Are there any preconditions on arr[n - 1]? Commented Jan 11, 2023 at 0:02
  • No, it's just contain an integer, the user will input the array Commented Jan 11, 2023 at 0:03
  • What is the time complexity each iteration of the loop? Commented Jan 11, 2023 at 0:07
  • This question needs more context. Is this an exercise you have been given as part of a course or textbook, or is it an example you invented yourself? If the former, please give all relevant details. Commented Jan 11, 2023 at 0:08
  • It's example I invented in order to understand complexity. Suppose each itaration is O(1) for example only printing "*" Commented Jan 11, 2023 at 0:14

1 Answer 1

Reset to default
1

The time complexity of your code only depends on the value of the element at index n-1. Suppose that element in your array has the value m. Then you can consider the time complexity of your code to be O(m).

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Why does it different from itarating for declared length by the code?
You are iterating as many times as the value at index n - 1. This is quite similar to looping through an array of size n. In your case, the n is equal to the value at index n - 1 of the array. Consider that value to be an unknown variable m. So your complexity is O(m). The number of iterations in your code does not depend on the length of the array so the time complexity cannot be O(n).
But eventually it's constant so how this is different from declaring a variable and put the last index inside it O(1) and then itarating for this variable which is constant so also O(1)?
The difference between the case above and explicitly declaring a variable's value is that in the second case, the value of the variable is known. Thus, we know that the code will take constant time. If the value of the variable is unknown, we do not how much time it will take, but we know that the time is dependent on the value it will eventually take. If we denote that unknown value with the variable m, the time complexity will be O(m). I.e. the larger the value of m, the more time it will take!
@Newlearner826 Why do you say m is constant? Surely your algorithm works for different arrays, and their last element can differ. Since the time complexity depends on this element, then this is the variable you are interested in.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.